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
}
No.42 接雨水
上面是由数组 [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,当下次遇到大于行高值的值时,将临时储水量添加到总量中去,然后重置临时储水量,循环直到行高达到最大高度值。
代码:
找出最大值,两侧向最大值靠拢
同样,首先找出最大值,但是本次获取的是最大值的索引,以最大值索引为边界,遍历最大值两侧的区间。 左区间,以起始值为左侧的最高值(因为第一位和最后一位是边界值,均不能存储水),从1开始遍历,若当前值小于当前区间最大值,其之间的落差即为该点上的最大储水量;若当前值大于当前区间的最大值,则把该区间的最大值更新为当前值,如此类推 右区间也一样,只不过遍历是从数组末尾开始。
代码:
参考: 详细通俗的思路分析,多解法 --- windliang 找规律,透过现象看本质