接雨水: 两堵墙之间能装多少水?
从「每一格怎么算水」到「双指针为什么安全」, 看懂这道经典高频题。
给定一排柱子高度, 凹陷处下雨能接多少水。 核心公式 water[i] = max(0, min(leftMax, rightMax) − height[i])。本页用峡谷防洪实验室 4 层递进, 把双指针的 O(n)/O(1) 解法讲透。
单格公式: 水量 = min(左最高墙, 右最高墙) − height[i]
以 index = 5 (高度 0) 为例。它左边能找到的最高墙是 2, 右边能找到的最高墙是 3。
公式推导
- 左边最高墙2
- 右边最高墙3
- 水位 = min(2, 3)2
- 当前柱子高度 height[5]0
- 接水 = 水位 − 高度 = 2 − 02
为什么是 min 不是 max
想象左右两堵真实的墙: 水位再高也只能到 *较矮的那一堵* 的顶, 再往上水就会从矮的一侧漏走。 所以单格水位永远由较矮一侧决定。
预处理 leftMax / rightMax — 用空间换时间
逐格暴力扫描左右最高墙是 O(n²)。 把“从左累计的最高”和“从右累计的最高”先扫两遍存下来, 每一格就能 O(1) 出答案 — 时间 O(n), 空间 O(n)。
| 数组 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 |
|---|---|---|---|---|---|---|---|---|---|---|---|---|
| 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 |
| min(L,R) | 0 | 1 | 1 | 2 | 2 | 2 | 2 | 3 | 2 | 2 | 2 | 1 |
| − height | 0 | 0 | 1 | 0 | 1 | 2 | 1 | 0 | 0 | 1 | 0 | 0 |
预处理思路
从左往右扫一遍存 leftMax[i]; 从右往左扫一遍存 rightMax[i]。 然后每一格的水量就是 min(leftMax[i], rightMax[i]) − height[i]。代价: 两个长度 n 的辅助数组, 空间 O(n)。
进阶: 压成两个变量
观察上表会发现 — 我们从来不需要“过去”的 leftMax / rightMax 全部历史, 只需要当前指针扫过的最大值。因此可以用两个变量 leftMax、rightMax 配合双指针走到底, 空间立刻从 O(n) 降到 O(1)。这就是下一节“双指针主动画”要演示的核心。
双指针主动画 — 较矮一侧, 安全结算
每一步只处理较矮一侧。左侧短就更新 leftMax 并结算 l 列, 右侧短就更新 rightMax 并结算 r 列, 然后较矮指针向中间走一位。 看石柱怎么一格一格变成已结算的灰蓝色, 透明水体怎么填进坑里。
透明蓝水体 = 当前位置已结算的接水量; 灰蓝石柱 = 指针已经走过, 不会再变; 左右两侧发光水位尺标记 leftMax / rightMax; 右侧量杯实时累计 total。
指针 / Max 状态
- l
- 0
- r
- 11
- leftMax
- 0
- rightMax
- 0
- 本步 +water
- 0
- total
- 0
双指针的全部秘密: 较矮一侧的水位上限已经被另一侧的更高柱子框死, 可以安全结算。
1func trap(height []int) int {2 l, r := 0, len(height)-13 leftMax, rightMax := 0, 04 ans := 056 for l < r {7 if height[l] < height[r] {8 if height[l] >= leftMax {9 leftMax = height[l]10 } else {11 ans += leftMax - height[l]12 }13 l++14 } else {15 if height[r] >= rightMax {16 rightMax = height[r]17 } else {18 ans += rightMax - height[r]19 }20 r--21 }22 }2324 return ans25}
步骤时间线
30 秒面试版答案
这题本质是: 每个位置的水量 = min(左最高墙, 右最高墙) − height[i]。
暴力对每个位置左右扫描求最高墙, O(n²); 预处理 leftMax/rightMax 数组做到 O(n) 时间 O(n) 空间; 双指针进一步把两个数组压缩成两个变量。
双指针从两端出发, 维护 leftMax / rightMax。 每次处理较矮一侧 — 因为较矮一侧的水位上限已经被另一侧的更高柱子框死, 可以安全结算。结算后指针向中间走一位, 最终累计所有位置的水量。
时间 O(n), 空间 O(1)。
- 水位看两堵墙的较矮那堵
- 处理较矮一侧, 因为它的上限确定了
- 两个 max 变量足以代替两个 max 数组
- 指针相遇即结束, 累计就是答案
常见疑问
- 问 1: 为什么处理较矮一侧而不是较高一侧?答: 较矮一侧的水位上限由该侧的 max 决定; 另一侧已经存在更高的柱子, 不可能让水位涨过较矮侧的 max。
- 问 2: 本步水量算负数怎么办?答: 当 height[i] >= 该侧 max 时, max 直接刷新成 height[i], water 写成 max(0, max−h) 自然为 0。永远不会出现负数。
- 问 3: 和 LC11 盛水容器有什么区别?答: LC11 求两根柱子之间最大面积 — 短板决定水位; LC42 求所有间隙总积水量 — 每格独立, 较矮侧 max 决定水位。两题都靠 「较矮一侧已被另一侧框死」 做安全结算。
扩展思路
本题还有一种 单调栈解法: 维护一个单调递减的“未封顶”柱子下标栈, 遇到更高柱子就把栈顶 *横向* 一层一层接走。 与双指针不同的是, 单调栈一次性处理水平方向的一整层水, 而双指针逐格累加。 两种解法时间都是 O(n), 实现细节不同 — 本页主动画专注双指针, 单调栈适合理解柱状图类问题(如 LC84) 时再单独学习。