给定 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;
};
参考思路

暴力，双数组。