42.接雨水

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

示例 1：

img

1
2
3
输入：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：

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

Solution：

image-20240522162520340

用单调栈的思路思考，当遇到比栈顶元素a高的元素b时，将栈顶元素出栈，将新的栈顶元素记为c，那么高为min(b,c)-a，宽为(b - c - 1）

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
26
27
28
29
class Solution {
    public int trap(int[] height) {
        int ans = 0;  // 初始化结果变量，存放能接的雨水总量
        Deque<Integer> st = new ArrayDeque<>();  // 创建一个栈，用于存放高度数组的索引
        
        // 遍历高度数组
        for (int i = 0; i < height.length; i++) {
            // 当栈不为空且当前高度大于等于栈顶索引对应的高度时
            while (!st.isEmpty() && height[i] >= height[st.peek()]) {
                int bottomH = height[st.pop()];  // 弹出栈顶索引并获取其对应的高度，作为凹槽底部高度
                
                // 如果栈为空，则没有左边的边界，跳出循环
                if (st.isEmpty()) {
                    break;
                }
                
                int left = st.peek();  // 获取新的栈顶索引，作为凹槽左边界
                int dh = Math.min(height[left], height[i]) - bottomH;  // 计算凹槽的有效高度
                ans += dh * (i - left - 1);  // 计算凹槽面积并累加到总量中
            }
            
            // 将当前索引入栈
            st.push(i);
        }
        
        return ans;  // 返回能接的雨水总量
    }
}