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

https://jangdelong.github.io/blog_img/images/leetcode-42/rainwatertrap.png

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

示例:

1
2
输入: [0,1,0,2,1,0,1,3,2,1,2,1]
输出: 6
参考解答
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
/**
* @param {number[]} heights
* @return {number}
*/
var trap = function(heights) {
var len = heights.length;
var res = 0;
var max = 0;
var leftMaxs = [];
var rightMaxs = [];

for (var i = 0; i < len; i++) {
leftMaxs[i] = max = Math.max(max, heights[i]);
}
max = 0;
for (var j = len -1; j >= 0; j--) {
rightMaxs[j] = max = Math.max(max, heights[j]);
}

for (var k = 0; k < len; k++) {
res += Math.min(leftMaxs[k], rightMaxs[k]) - heights[k];
}

return res;
};
参考思路

暴力,双数组。