leetcode-42-接雨水

题目地址

给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。

示例 1：

输入： height = [0,1,0,2,1,0,1,3,2,1,2,1]
输出： 6
解释： 上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图，在这种情况下，可以接 6 个单位的雨水（蓝色部分表示雨水）。 

示例 2：

输入： height = [4,2,0,3,2,5]
输出： 9

提示：

• n == height.length
• 1 <= n <= 2 * 104
• 0 <= height[i] <= 105

解题思路

这道题初始看可能感觉无从下手，如何计算是示例1中每一个凹坑中的面积呢？如果陷入这种思路是很难解出本题的。 想接到雨水，就要两边柱子高，中间柱子矮，这样才能接到雨水，所以我们可以先找到最高的柱子，这样，只要有一个柱子它和最高柱子之间有比它矮的柱子，就可以接到雨水。 以示例1为例，最高的柱子是 3，下标 0 位置的右侧有下标 1 比它矮，则此处可以接到的雨水就是下标 0 的高度减去下标 1 的高度。 依次向右遍历，直到最高的柱子为止，要注意在遍历过程中，需要尝试更新左侧最高柱子的高度，右侧同理。

代码实现

var trap = function(height) {
    const len = height.length
    let maxInd = 0
    let res = 0

    // 获取最高点下标
    for(let i = 1;i<len;i++){
        if(height[i]>height[maxInd]){
            maxInd = i
        }
    }

    // 计算最高点左边可以接到的雨水
    let curMax = 0
    for(let i = 1;i<maxInd;i++){
        if(height[i]>height[curMax]){
            curMax = i
        }

        res += height[curMax]-height[i]
    }

    // 计算最高点右边可以接到的雨水
    curMax = len-1

    for(let i = len-2;i>maxInd;i--){
        if(height[i]>height[curMax]){
            curMax = i
        }

        res += height[curMax]-height[i]
    }

    return res
}

至此我们就完成了 leetcode-42-接雨水

如有任何问题或建议，欢迎留言讨论！