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

1
2

输入：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

class Solution {
public:
    /*
    * ## 解题思路
    * * 双指针法
    * 1. 分别用l,r指向数组左右边界；
    * 2. 依次判断height[l], height[r]大小，将小的指针向中间移动一格，同时记录小的高度lower
    * 3. 根据当前lower, 更新已经扫描过的(两外侧)柱子的较低高度level；
    * 4. 当前柱子能够接的雨水为level-lower；
    * 5. 总雨水量就是将每个柱子接水量的和；
    */
    int trap(vector<int>& height) {
        int l = 0;
        int r = height.size() - 1;
        int level = 0; //外侧(已经遍历过的)最高高度，为桶壁高度
        int water = 0; //总水量
        while (l<r) {
            int lower = height[ height[l] < height[r] ? l++: r-- ];
            level = max(level, lower);
            water += level - lower;
        }

        return water;
    }
};

 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
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68

// @lc code=start
impl Solution {
    /// ## 解题思路
    /// - 双指针
    /// 1.
    /// 对于每一列height[i],其盛水的量由左右两边中较低的边沿确定,而每边的边沿为这边中所有边界的最大值,用公式表示
    ///    桶边界为 $ h_edge[i] = max(height[i], min(max(height[..i]), max(height[i+1..]))) $
    ///    盛水量为: $ water[i] = h_edge[i] - height[i] $
    ///    总盛水量: $ waters = sum(water[..]) $
    /// 2. 为了计算每列的桶边界, 设置双指针l,r=0, n-1;
    /// 3. 如果height[l] < height[r], 则对于i=l的列, 其桶边界必定在左边即:
    ///     $ h_edge = max(height[..l], height[l]) $
    ///    否则对与i=r的列, 桶边界为:
    ///     $ h_edge = max(height[r+1..], height[r]) $
    /// 4. 综合以上2种情况,当l,r都从外向内移动时,可以用一个变量来记录h_edge;
    pub fn trap(height: Vec<i32>) -> i32 {
        let (mut l, mut r) = (0, height.len() - 1);
        let mut h_edge = 0; //当前列的桶边界
        let mut water = 0;
        while l < r {
            let hi = if height[l] < height[r] {
                l += 1;
                height[l - 1]
            } else {
                r -= 1;
                height[r + 1]
            };
            h_edge = h_edge.max(hi);
            water += h_edge - hi;
        }

        water
    }

    /// ## 解题思路2
    /// - 单调栈
    /// 1. 设置单调递减栈desc_wall, 用于保存height中;
    /// 2. 从左->右遍历height;
    /// 3. 如果栈为空或当前柱子height[i] < 栈顶柱子高度, 则当前柱子可能会积水. 将当前柱子索引i入栈;
    /// 4. 如果当前柱子高度height[i] > 栈顶柱子高度, 则
    pub fn trap2(height: Vec<i32>) -> i32 {
        let mut total = 0;
        let mut desc_wall = Vec::with_capacity(height.len());
        for (i, &h) in height.iter().enumerate() {
            // 如果栈不为空, 且当前柱子高度 > 栈顶柱子高度, 则可能会积水
            while !desc_wall.is_empty() && h > height[*desc_wall.last().unwrap()] {
                let bottom_i = desc_wall.pop().unwrap(); // 栈顶为积水底部

                // 如果左侧有更高的柱子, 则可以积水
                if let Some(&left_i) = desc_wall.last() {
                    let width = (i - left_i - 1) as i32; // 积水区宽度为:当前柱子 到 左边高柱子之间的部分
                    let min_wall = h.min(height[left_i]); // 积水区高度为: 左右两侧高度中较低的
                    total += width * (min_wall - height[bottom_i]);
                }
            }
            // 栈中所有低于当前高度的柱子已经处理完
            // 栈顶柱子高度 > 当前柱子高度, 则可能会积水(当后面有柱子高于当前柱子时)
            desc_wall.push(i); // 入栈, 等后续出现高于当前高度的柱子时处理
        }

        total
    }
}
// @lc code=end

struct Solution;