算法 - 接雨水

Posted on

1. 题目

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

示例:

1
2
3
4
5
输入: height = [0,1,0,2,1,0,1,3,2,1,2,1]
输出: 6

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

2. 解题思路

核心视角：按列计算。对每一列 i，它能接的水 = min(左侧最高, 右侧最高) - height[i]（若为负则 0）。「木桶效应」取决于两边较矮的那个挡板。

2.1 动态规划预处理左右最大值

开两个数组 leftMax[i]、rightMax[i] 分别预处理「从两端到 i 的最大高度」，再逐列累加。O(n) 时间、O(n) 空间。

2.2 双指针（最优）

左右指针 l、r 向中间逼近，维护 leftMax、rightMax 两个标量：

  • 比较 height[l] 与 height[r]，较矮的一侧决定该侧列的接水量：

    • 若 height[l] < height[r]：左列的左挡板是 leftMax，右挡板至少是 height[r]（≥ height[l]），所以左侧当前列水位由 leftMax 决定 → 累加 leftMax - height[l]，l++。
    • 右侧对称处理。

  • 边走边更新各自的 max。

  • 时间复杂度：O(n)，空间复杂度：O(1)。

3. TypeScript 实现

3.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
function trap(height: number[]): number {
    let l = 0;
    let r = height.length - 1;
    let leftMax = 0;
    let rightMax = 0;
    let water = 0;

    while (l < r) {
        if (height[l] < height[r]) {
            if (height[l] >= leftMax) {
                leftMax = height[l];       // 新的左挡板
            } else {
                water += leftMax - height[l]; // 填补凹处
            }
            l++;
        } else {
            if (height[r] >= rightMax) {
                rightMax = height[r];
            } else {
                water += rightMax - height[r];
            }
            r--;
        }
    }

    return water;
}

console.log(trap([0,1,0,2,1,0,1,3,2,1,2,1])); // 6

3.2 DP 预处理左右最大值

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
function trapDP(height: number[]): number {
    const n = height.length;
    if (n === 0) return 0;
    const leftMax = new Array(n).fill(0);
    const rightMax = 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]);

    rightMax[n - 1] = height[n - 1];
    for (let i = n - 2; i >= 0; i--) rightMax[i] = Math.max(rightMax[i + 1], height[i]);

    let water = 0;
    for (let i = 0; i < n; i++) water += Math.min(leftMax[i], rightMax[i]) - height[i];

    return water;
}

4. 面试延伸

  • 栈解法：用单调递减栈按「行」积水（遇到更高柱子就弹出凹槽结算宽度），思路另类，可作加分。
  • 与盛最多水的容器对照：那道是「两条板一次盛水」，本题是「每列独立按左右挡板蓄水」，都是双指针经典，但计算方式不同。
  • 追问：为什么 height[l] < height[r] 时能直接对左列结算？因为右挡板已被 height[r] 保证不矮于当前左侧，水位由 leftMax 唯一确定，无需求真实的右侧最大值。

难度：困难 | LeetCode 42 | 双指针 / 单调栈