跳到主要内容

接雨水

问题​

给定 n 个非负整数表示每个宽度为 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

来源：LeetCode 42. 接雨水

答案​

方法一：双指针（推荐，最优）​

核心思路：每个位置能接的水 = min(左边最高, 右边最高) - 自身高度。使用双指针从两端向中间逼近，维护左右最大值。

trapTwoPointers.ts
function trap(height: number[]): number {
  let left = 0;
  let right = height.length - 1;
  let leftMax = 0;
  let rightMax = 0;
  let water = 0;

  while (left < right) {
    if (height[left] < height[right]) {
      // 左边较矮，水量由左边最高决定
      if (height[left] >= leftMax) {
        leftMax = height[left]; // 更新左边最高
      } else {
        water += leftMax - height[left]; // 接水
      }
      left++;
    } else {
      // 右边较矮，水量由右边最高决定
      if (height[right] >= rightMax) {
        rightMax = height[right];
      } else {
        water += rightMax - height[right];
      }
      right--;
    }
  }

  return water;
}

图解关键直觉：

位置 i 能接的水取决于 min(leftMax, rightMax) - height[i]

当 height[left] < height[right] 时：
- 我们确定 rightMax >= height[right] > height[left]
- 所以 min(leftMax, rightMax) = leftMax
- 水量 = leftMax - height[left]（如果 > 0）

反过来同理。这就是为什么双指针能正确工作的原因。
复杂度分析
  • 时间复杂度：O(n)O(n) — 一次遍历
  • 空间复杂度：O(1)O(1) — 常数空间

这是最优解！

方法二：预计算左右最大值​

更容易理解的方法：先预计算每个位置左边和右边的最大高度。

trapPrecompute.ts
function trap(height: number[]): number {
  const n = height.length;
  if (n < 3) return 0;

  // leftMax[i]: 位置 i 左边（含自身）的最高柱子
  const leftMax = new Array(n);
  leftMax[0] = height[0];
  for (let i = 1; i < n; i++) {
    leftMax[i] = Math.max(leftMax[i - 1], height[i]);
  }

  // rightMax[i]: 位置 i 右边（含自身）的最高柱子
  const rightMax = new Array(n);
  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;
}

图解：

height:   [0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1]
leftMax:  [0, 1, 1, 2, 2, 2, 2, 3, 3, 3, 3, 3]
rightMax: [3, 3, 3, 3, 3, 3, 3, 3, 2, 2, 2, 1]

water[i] = min(leftMax[i], rightMax[i]) - height[i]
         = [0, 0, 1, 0, 1, 2, 1, 0, 0, 1, 0, 0]

总和 = 6

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

方法三：单调栈​

核心思路：维护一个单调递减栈。遇到比栈顶高的柱子时，说明形成了一个"槽"，可以接水。

trapStack.ts
function trap(height: number[]): number {
  const stack: number[] = []; // 存索引
  let water = 0;

  for (let i = 0; i < height.length; i++) {
    // 当前柱子比栈顶高，形成凹槽
    while (stack.length > 0 && height[i] > height[stack[stack.length - 1]]) {
      const bottom = stack.pop()!; // 凹槽底部

      if (stack.length === 0) break; // 左边没有更高的柱子了

      const left = stack[stack.length - 1]; // 左边界
      const width = i - left - 1;
      const h = Math.min(height[left], height[i]) - height[bottom];
      water += width * h;
    }

    stack.push(i);
  }

  return water;
}
单调栈的思路

想象水是一层一层横着填的。每次遇到比栈顶高的柱子，就把中间的凹槽填平一层。

这与前两种方法的"每根柱子竖着算水量"思路不同。

三种方法对比​

方法时间空间难度面试推荐
双指针O(n)O(n)O(1)O(1)★★★★最优解
预计算O(n)O(n)O(n)O(n)★★最好理解
单调栈O(n)O(n)O(n)O(n)★★★思路新颖

常见面试追问​

Q1: 如果柱子有宽度（不只是 1）呢？​

答案：给每个柱子一个宽度，接水时要乘以宽度。本质思路不变，只是计算面积时需要考虑宽度。

Q2: 盛最多水的容器？(LeetCode 11)​

答案：这是接雨水的简化版——两根柱子之间直接盛水（不考虑中间的柱子）：

function maxArea(height: number[]): number {
  let left = 0;
  let right = height.length - 1;
  let maxWater = 0;

  while (left < right) {
    const water = Math.min(height[left], height[right]) * (right - left);
    maxWater = Math.max(maxWater, water);

    // 移动较矮的一端
    if (height[left] < height[right]) {
      left++;
    } else {
      right--;
    }
  }

  return maxWater;
}

Q3: 接雨水 II（3D 版）？(LeetCode 407)​

答案：用优先队列（最小堆），从外围开始向内"灌水"：

// 伪代码思路
// 1. 将所有边界格子加入最小堆
// 2. 每次取出最矮的格子
// 3. 检查它的邻居：如果邻居更矮，可以接水；否则更新边界
// 4. 将邻居加入堆
// 时间复杂度：O(mn log(mn))

Q4: 为什么双指针方法中 min(leftMax, rightMax) 的推理是正确的？​

答案：

假设 height[left] < height[right]：

  • rightMax >= height[right] > height[left]
  • 所以真正的 rightMax（整个右侧最大值）一定 ≥ height[right]
  • 而 leftMax 我们已经精确计算了
  • 因此 min(leftMax, rightMax) 就等于 leftMax（因为 rightMax 一定更大）

这就是为什么我们只需要维护一边的最大值就够了。

相关链接​