[leetcode]No.42 接雨水

[liangbus]

No.42 接雨水

42. 接雨水
    给定 n 个非负整数表示每个宽度为 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，当下次遇到大于行高值的值时，将临时储水量添加到总量中去，然后重置临时储水量，循环直到行高达到最大高度值。

代码：

var trap = function(height) {
    let topHeight = getTopHeight(height)
    let res = 0
    let tmp = 0 // 临时累计
    let collect = false // 临时累加标记
    for(let rowHeight = 1; rowHeight <= topHeight; rowHeight++) {
        tmp = 0
        collect = false
        for(let j = 0; j < height.length; j++) {
            if(collect && height[j] < rowHeight) {
                tmp++
            }
            if(height[j] >= rowHeight) {
                res += tmp
                tmp = 0
                collect = true
            }
        }
    }
    return res
};

function getTopHeight(arr) {
    let top = arr[0]
    let index = 0
    arr.forEach((h, i) => {
        if(h > top) {
            top = h
            index = i
        }
    })
    return index
}

找出最大值，两侧向最大值靠拢

同样，首先找出最大值，但是本次获取的是最大值的索引，以最大值索引为边界，遍历最大值两侧的区间。
左区间，以起始值为左侧的最高值（因为第一位和最后一位是边界值，均不能存储水），从1开始遍历，若当前值小于当前区间最大值，其之间的落差即为该点上的最大储水量；若当前值大于当前区间的最大值，则把该区间的最大值更新为当前值，如此类推
右区间也一样，只不过遍历是从数组末尾开始。

代码：

var trap = function(height) {
    let topIndex = getTopHeight(height)
    let res = 0
    let i = 1
    let cur = height[0]
    // left side of the MAX column
    for(; i < topIndex; i++){
        if(height[i] < cur) {
            res += cur - height[i]
        } else {
            cur = height[i]
        }
    }
    // The right side
    cur = height[height.length - 1]
    for(i = height.length - 2; i > topIndex; i--) {
        if(height[i] < cur) {
            res += cur - height[i]
        } else {
            cur = height[i]
        }
    }
    return res
}

function getTopHeight(arr) {
    let top = arr[0]
    let index = 0
    arr.forEach((h, i) => {
        if(h > top) {
            top = h
            index = i
        }
    })
    return index
}

参考：
详细通俗的思路分析，多解法 --- windliang
找规律，透过现象看本质