Loading...
墨滴

叫我詹躲躲

2021/04/02  阅读:24  主题:兰青

【算法】[困难]-直方图的水量-动态规划

17.21. 直方图的水量

难度:[困难]

给定一个直方图(也称柱状图),假设有人从上面源源不断地倒水,最后直方图能存多少水量?直方图的宽度为 1。

上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的直方图,在这种情况下,可以接 6 个单位的水(蓝色部分表示水)。 感谢 Marcos 贡献此图。

示例:

输入: [0,1,0,2,1,0,1,3,2,1,2,1]
输出: 6

动态规划

1.记录height中的每个元素,从左向右扫描并记录右边的最大高度;
2.记录height中的每个元素,从右向左扫描并记录右边的最大高度;
3.将左右位置元素对比取最小的元素,减去数组当前元素的高度。

从左向右扫描并记录右边的最大高度
从右向左扫描并记录右边的最大高度
取高度最小值

Javascript

var trap = function (height{
    let len = height.length
    if (len === 0return 0
    //记录左边每个矩形最大高度
    let left = Array(len).fill(0)
    left[0] = height[0]
    for (let i = 1; i < len; ++i) {
        left[i] = Math.max(left[i - 1], height[i])
    }
    //记录右边每个矩形最大高度
    let right = Array(len).fill(0)
    right[len - 1] = height[len - 1]
    for (let i = len - 2; i >= 0; --i) {
        right[i] = Math.max(right[i + 1], height[i])
    }
    //记录结果
    let ret = 0
    for (let i = 0; i < len; ++i) {
        //左右对比取最小边界,减去当前矩形高度
        ret += Math.min(left[i], right[i]) - height[i]
    }
    return ret
};

go

func trap(height []int) int {
 n := len(height)
 if n == 0 {
  return 0
 }
 //记录左边每个元素最大高度
 leftMax := make([]int, n)
 leftMax[0] = height[0]
 for i := 1; i < n; i++ {
  leftMax[i] = max(leftMax[i-1], height[i])
 }
 //记录左边每个元素最大高度
 rightMax := make([]int, n)
 rightMax[n-1] = height[n-1]
 for i := n - 2; i >= 0; i-- {
  rightMax[i] = max(rightMax[i+1], height[i])
 }
 fmt.Println(leftMax, rightMax)
 ret := 0
 for j := 0; j < n; j++ {
  ret += (min(leftMax[j], rightMax[j]) - height[j])
 }
 return ret
}

//由于Go语言里面没有max(),min()需要自己实现一个
func max(a, b int) int {
 if a-b > 0 {
  return a
 }
 return b
}
func min(a, b int) int {
 if a-b > 0 {
  return b
 }
 return a
}

Typescript

function trap(height{
    var len = height.length;
    if (len === 0)
        return 0;
    //记录左边每个矩形最大高度
    var left = Array(len);
    left[0] = height[0];
    for (var i = 1; i < len; ++i) {
        left[i] = Math.max(left[i - 1], height[i]);
    }
    //记录右边每个矩形最大高度
    var right = Array(len);
    right[len - 1] = height[len - 1];
    for (var i = len - 2; i >= 0; --i) {
        right[i] = Math.max(right[i + 1], height[i]);
    }
    //记录结果
    var ret = 0;
    for (var i = 0; i < len; ++i) {
        //左右对比取最小边界,减去当前矩形高度
        ret += Math.min(left[i], right[i]) - height[i];
    }
    return ret;
}

python

class Solution(object):
    def trap(self, height):
        """
        :type height: List[int]
        :rtype: int
        """

        if not height:
            return 0
        # 数组长度
        n = len(height)

        # 记录左边每个矩形最大高度
        left = [0]*n
        left[0] = height[0]
        for i in range(1,n):
            left[i] = max(left[i - 1], height[i])

        # 记录右边每个矩形最大高度
        right = [0]*n
        right[n - 1] = height[n - 1]
        for i in range(n-2,-1,-1):
            right[i] = max(right[i + 1], height[i])
        # 记录结果
        ret = sum(min(left[i], right[i]) - height[i] for i in range(n)) 
        return ret

叫我詹躲躲

2021/04/02  阅读:24  主题:兰青

作者介绍

叫我詹躲躲

zhanhongzhu.top