接雨水

更新: 7/3/2026 字数: 0 字时长: 0 分钟

LeetCode 第 42 题 · 困难 · 双指针 / 单调栈 / 动态规划经典题

题目描述

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

直观理解

把数组 height 想象成一排高低不平的墙。下雨后，每个"凹槽"能存住的水，取决于它左右两侧最高墙中较矮的那一堵——因为水会从矮的一侧溢出去。

示例：

输入	输出	说明
`[0,1,0,2,1,0,1,3,2,1,2,1]`	`6`	凹槽逐格蓄水，合计 6 单位
`[4,2,0,3,2,5]`	`9`	左墙 4、右墙 5，中间大坑蓄满
`[1,1,1]`	`0`	平地无凹槽
`[]`	`0`	空数组

接雨水示意图：蓝色高低柱子形成的凹槽中蓄着半透明蓝色雨水

思路拆解：从暴力到双指针

核心原理：逐列计算

无论用哪种解法，本题的灵魂只有一句话——对每一列，它能接的水 = min(左侧最高, 右侧最高) − 当前列高度（结果为负则取 0）。

把每一列的蓄水量加起来，就是答案。

第一步：暴力枚举（先解出来）

最直接的想法——对每一根柱子 i，分别向左、向右扫描一遍，找出左边最高 leftMax 和右边最高 rightMax，代入上面的公式。

外层遍历每列，内层左右扫描各，总时间复杂度。思路清晰但重复扫描严重。

点击展开暴力解法（仅供理解，不推荐）

function trap_bruteForce(height) {
  let total = 0;
  for (let i = 0; i < height.length; i++) {
    let leftMax = 0, rightMax = 0;
    // 向左找最高
    for (let l = i; l >= 0; l--) leftMax = Math.max(leftMax, height[l]);
    // 向右找最高
    for (let r = i; r < height.length; r++) rightMax = Math.max(rightMax, height[r]);
    // 当前列蓄水量
    total += Math.min(leftMax, rightMax) - height[i];
  }
  return total;
}

第二步：动态规划（用空间换时间）

暴力法反复扫描求 leftMax / rightMax，其实这两个值可以预处理：

leftMax[i] = 从左到右的前缀最大值；
rightMax[i] = 从右到左的后缀最大值。

预处理后再遍历一次求和，时间降到，但需要两个额外数组，空间。

点击展开动态规划解法

function trap_dp(height) {
  const n = height.length;
  if (n === 0) return 0;
  const leftMax = new Array(n), rightMax = new Array(n);
  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 total = 0;
  for (let i = 0; i < n; i++) total += Math.min(leftMax[i], rightMax[i]) - height[i];
  return total;
}

第三步：双指针（最优，空间降到 O(1)）

DP 解法要存两个数组，其实没必要。关键观察：

当我们从两端向中间收缩时，如果 height[left] < height[right]，那么对于 left 这一列，右侧一定存在一堵 ≥ height[right] 的墙，所以它的蓄水量只由 leftMax 决定，与右侧具体多高无关。

这意味着：哪一侧的柱子矮，就结算哪一侧——矮的一侧才是短板，水位由它这边的最大值封顶。

核心思路

用 left、right 双指针从两端向中间逼近，同时维护 leftMax、rightMax。每一步比较 height[left] 与 height[right]：

左边矮 → 结算 left：若 height[left] ≥ leftMax 就更新 leftMax，否则累加 leftMax − height[left]，然后 left++；
右边矮（或相等） → 对称处理 right。

因为矮的一侧短板已确定，无需知道对面精确高度，只需遍历一遍、额外空间即可。

双指针示意图：柱状图两端各有一个向中间移动的指针，标注 leftMax 与 rightMax 两堵挡水墙

交互式动画演示

下面用样例 [0,1,0,2,1,0,1,3,2,1,2,1] 完整演示双指针解法。点击 下一步 / 自动播放，观察 left、right 指针如何向中间逼近，leftMax / rightMax 如何更新，以及每根柱子上方蓝色积水的累加：

双指针 · 接雨水演示

样例输入：[0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1]

left0

right11

leftMax0

rightMax0

water0

初始化：left=0 指向最左，right=n-1 指向最右，leftMax=rightMax=0，总水量 water=0。

步骤 0 / 12

观察重点

绿色 L 是左指针，橙色 R 是右指针，黄色高亮为当前正在结算的柱子；
每一步只处理较矮的一侧；柱子上方的斜纹蓝色块就是该列接到的水；
water 只增不减，最终两指针相遇时即为答案 6。

完整代码（JavaScript）

/**
 * 接雨水 —— 双指针，时间 O(n)，空间 O(1)
 * @param {number[]} height
 * @return {number}
 */
function trap(height) {
  let left = 0;
  let right = height.length - 1;
  let leftMax = 0;   // [0, left] 区间的最大高度
  let rightMax = 0;  // [right, n-1] 区间的最大高度
  let water = 0;

  while (left < right) {
    // 关键：哪一侧矮就结算哪一侧，矮侧的短板已经确定
    if (height[left] < height[right]) {
      // 左边更矮：该列蓄水只取决于 leftMax
      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;
}

// 测试
console.log(trap([0,1,0,2,1,0,1,3,2,1,2,1])); // 6
console.log(trap([4,2,0,3,2,5]));             // 9
console.log(trap([1,1,1]));                   // 0
console.log(trap([]));                        // 0

复杂度分析

解法	时间复杂度	空间复杂度	说明
暴力枚举			每列都向左右各扫描一遍
动态规划			预存 `leftMax` / `rightMax` 两个数组
单调栈			逐层横向结算，栈存下标
双指针（最优）			两端逼近，只结算短板一侧

其中为柱子数量。双指针在时间与空间上都做到最优：

边界与易错点

易错点清单

空数组 / 长度 < 3：[]、[5]、[3,1] 均返回 0（不足以形成凹槽）。while (left < right) 天然覆盖。
结算方向判断：必须比较 height[left] < height[right] 决定结算哪一侧。相等时归入 else 分支（结算右侧）也可以，反过来同理，但两个分支的收缩逻辑不能写混。
先更新墙还是先加水：应先判断 height[left] >= leftMax——成立则更新 leftMax（此列不蓄水），否则才累加。顺序颠倒会把本该当墙的柱子错误计入蓄水。
累加的是差值不是高度：加的是 leftMax − height[left]，别写成 leftMax 或 height[left]。
指针只能向内移动：left 只增、right 只减，任何一步都要推进对应指针，否则死循环。
为什么双指针成立：结算左侧时用的是 leftMax，看似忽略了右侧，但进入该分支的前提是 height[left] < height[right]，保证右侧必有更高的墙兜底，水不会从右边漏走。

一句话记忆

"短板决定水位"——两端往里走，谁矮就结算谁，用它这一侧的历史最高墙减去自身高度就是蓄水量。

接雨水 ​

题目描述 ​

思路拆解：从暴力到双指针 ​

核心原理：逐列计算 ​

第一步：暴力枚举（先解出来） ​

第二步：动态规划（用空间换时间） ​

第三步：双指针（最优，空间降到 O(1)） ​

交互式动画演示 ​

完整代码（JavaScript） ​

复杂度分析 ​

边界与易错点 ​

接雨水