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

解题思路

核心思路是双指针边界，通过每个柱子能接住的雨水量取决于其左右两侧的最高柱子中较矮的那个（短板效应）：

  1. 边界定义：
    • 对于位置 i，左侧最高柱子高度为 left_max[i]；
    • 右侧最高柱子高度为 right_max[i]；
    • 位置 i 能接住的雨水量为 min(left_max[i], right_max[i]) - height[i]（若结果为正，否则为 0）。
  2. 优化实现：
    • 采用双指针法，无需额外存储 left_max 和 right_max 数组，将空间复杂度降至 O (1)；
    • 用 left 和 right 指针分别从左右两端向中间移动；
    • 用 left_max 和 right_max 记录当前左右侧的最高柱子高度；
    • 若 left_max < right_max：左侧柱子能接的雨水由 left_max 决定，移动左指针；
    • 否则：右侧柱子能接的雨水由 right_max 决定，移动右指针。

代码实现

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
class Solution {
public:
    int trap(vector<int>& height) {
        int n = height.size();
        if (n == 0) return 0;
        
        int left = 0;          // 左指针，从左侧开始
        int right = n - 1;     // 右指针，从右侧开始
        int left_max = 0;      // 左侧已遍历的最高柱子高度
        int right_max = 0;     // 右侧已遍历的最高柱子高度
        int result = 0;        // 雨水总量
        
        while (left < right) {
            // 左侧最高柱子低于右侧，左侧当前位置的雨水量由左侧决定
            if (height[left] < height[right]) {
                // 更新左侧最高柱子
                left_max = max(left_max, height[left]);
                // 累加雨水（若当前柱子低于左侧最高，则能接水）
                result += left_max - height[left];
                left++;
            } 
            // 右侧最高柱子低于或等于左侧，右侧当前位置的雨水量由右侧决定
            else {
                // 更新右侧最高柱子
                right_max = max(right_max, height[right]);
                // 累加雨水
                result += right_max - height[right];
                right--;
            }
        }
        
        return result;
    }
};