接雨水

给定 n 个非负整数表示每个宽度为 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 个单位的雨水（蓝色部分表示雨水）。

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

  • 输出：9

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
var trap = function(height) {
    const n = height.length;
    if (n == 0) {//极端情况
        return 0;
    }

    const leftMax = new Array(n).fill(0);//初始化从左往右看的最大值数组
    leftMax[0] = height[0];
    for (let i = 1; i < n; ++i) {
        leftMax[i] = Math.max(leftMax[i - 1], height[i]);
    }

    const rightMax = new Array(n).fill(0);//初始化从右往左看的最大值数组
    rightMax[n - 1] = height[n - 1];
    for (let i = n - 2; i >= 0; --i) {
        rightMax[i] = Math.max(rightMax[i + 1], height[i]);
    }

    let ans = 0;
  	//循环数组，每个位置能接的雨水量就是这个位置左右最大值的较小者减去当前的高度
    for (let i = 0; i < n; ++i) {
        ans += Math.min(leftMax[i], rightMax[i]) - height[i];
    }
    return ans;
};