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

示例 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 个单位的雨水（蓝色部分表示雨水）。

示例 2：

**输入：**height = [4,2,0,3,2,5]
**输出：**9

提示：

n == height.length

1 <= n <= 2 * 10(4)

0 <= height[i] <= 10(5)

每次只有遇到比前面高的方块时才需要更新ans，所以考虑使用单调栈

单调递减，栈顶小于当前元素时弹出，然后更新ans，更新时注意比较前一个元素与当前元素，取较小的值作为高

因为矮的元素会被弹出，所以我们必须记录下标索引，这样后面遇到高元素时才能同时考虑矮元素

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
    public : int trap(vector<int> &height) {
        stack<int> s;
        int len = height.size();
        int ans = 0;
        for (int i = 0; i < len; i++) {
            while (!s.empty() && height[s.top()] < height[i]) {
                int last = s.top();
                s.pop();

                if (s.empty())
                    break;

                int left = s.top();
                int w = i - left - 1;
                int h = min(height[left], height[i]) - height[last];
                ans += w * h;
            }
            s.push(i);
        }
        return ans;
    }
};

针对每个柱子分析，我们可以把所有柱子上的水加一起，

想知道每个柱子上有多少水，我们需要知道这根柱子左边最高多少，右边最高多少，然后取min减去当前即可

两次遍历分别获得向左向右看最高的柱子

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
int trap(vector<int>& height) {
int len = height.size();
if (len <= 1) return 0;

vector<int> left_max(len);
left_max[0] = height[0];
for (int i = 1; i < len; i++) left_max[i] = max(left_max[i - 1], height[i]);

vector<int> right_max(len);
right_max[len - 1] = height[len - 1];
for (int i = len - 2; i >= 0; i--) right_max[i] = max(right_max[i + 1], height[i]);

int ans = 0;
for (int i = 0; i < len; i++) ans += min(left_max[i], right_max[i]) - height[i];
return ans;
}
};

根据上述发现，每个柱子上的水只与左右较小的柱子有关，而且柱子本身也参与左右最高柱子的比较

我们可以用双指针l，r从两头向中间靠拢

当 height[l]<=height[r] 时，隐含了 l 处向右看最高值一定大于等于 height[l]，此时我们只要看 left_max 就能计算出 left 位置的水量。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
int trap(vector<int>& height) {
int len = height.size();
int l = 0, r = len - 1;
int left_max = 0, right_max = 0;
int ans = 0;
while (l < r) {
left_max = max(left_max, height[l]);
right_max = max(right_max, height[r]);
if (height[l] <= height[r]) {
ans += left_max - height[l];
l++;
} else {
ans += right_max - height[r];
r--;
}
}
return ans;
}
};