【LC 42】接雨水：四种解法其实在回答同一个问题，而三维版把它变成了 Dijkstra
适用读者：背过"双指针解接雨水"但一直没想明白为什么对的人；以及想知道单调栈到底在干什么的人
技术栈：Python 为主，附 Java 版
难度：Hard —— 但它的 Hard 之处不在代码长，而在核心论证：为什么"较矮的那一端"可以立刻结算
收获：四种解法其实是同一个问题的四种回答方式、双指针 O(1) 空间的正确性论证、单调栈"按层累加"的视角、以及 LC 407 三维版如何把这道题变成 Dijkstra
题目
给定
n 个非负整数表示每个宽度为
1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。
输入：height = [0,1,0,2,1,0,1,3,2,1,2,1]
输出：6
输入：height = [4,2,0,3,2,5]
输出：9
先提醒一句：
这两个示例的答案很容易记混 —— 第一个是
6，第二个是
9。
我自己第一次复盘这道题时就把
9 记成了第一个例子的答案，还顺手用反例验证了一下才确认。
把两个答案都钉死，后面推演时才有对照的锚点。
一、核心洞察：整道题只有一句话
无论用哪种解法，第一步都是把问题拆到"一个位置"上：
位置 i 能存多少水，只取决于它左边最高的柱子和它右边最高的柱子。
理由很朴素：水会往两边流，
能留住的高度是两侧的短板 —— 这就是木桶原理。写成公式：
water[i] = max(0, min(左最高, 右最高) - height[i])
拿第一个例子验证一下位置
5（高度
0）：它左边最高是
2（位置 3 那根），右边最高是
3（位置 7 那根），短板是
2，所以这格能存
2 - 0 = 2 单位水 —— 整个例子最大的一格。
所以
这道题从头到尾只在问一件事：
每个位置的"左最高"和"右最高"分别是多少？
接下来你会看到，所谓"四种解法"，其实只是
四种获取这两个数的方式。
二、四种解法：同一个问题的四种回答
先看最朴素的两个，它们是理解后两个的台阶。
暴力：对每个位置
i，往左扫一遍求最大、往右扫一遍求最大。正确，但每个位置都要
O(n)，总共
O(n²)。
动态规划：发现"往左扫"的结果可以复用 —— 开两个数组，
leftMax[i] 表示
[0..i] 的最大值，
rightMax[i] 表示
[i..n-1] 的最大值，各扫一遍预处理出来，然后每个位置
O(1) 查表：
def trap(height):
n = len(height)
leftMax = [0] * n # leftMax[i] = max(height[0..i])
rightMax = [0] * n # rightMax[i] = max(height[i..n-1])
leftMax[0] = height[0]
for i in range(1, n):
leftMax[i] = max(leftMax[i - 1], height[i])
rightMax[n - 1] = height[n - 1]
for i in range(n - 2, -1, -1):
rightMax[i] = max(rightMax[i + 1], height[i])
return sum(min(leftMax[i], rightMax[i]) - height[i] for i in range(n))
时间降到
O(n)，但开了两个数组，空间
O(n)。
接下来的问题就变成了：能不能不算出完整的两个数组？
三、双指针：完整代码
双指针的答案，是把"预处理"变成"边走边算"：
def trap(height):
l, r = 0, len(height) - 1
left_max = right_max = 0
ans = 0
while l < r:
if height[l] < height[r]:
left_max = max(left_max, height[l]) # ① 先更新
ans += left_max - height[l] # ② 再结算
l += 1
else:
right_max = max(right_max, height[r])
ans += right_max - height[r]
r -= 1
return ans
先看写法上的一个细节：
left_max 必须先更新再结算。
left_max = max(left_max, height[l]) # ① 先更新
ans += left_max - height[l] # ② 再结算
这个顺序让"新高"的情况自动消零：当
height[l] 就是新的左侧最高时，
left_max 被更新成
height[l]，于是
left_max - height[l] = 0，
不用写 if 特判。反过来先结算再更新，新高那格会算出
负数，把总量往回扣。
四、动画怎么看
画面里是一排柱子（浅米色），
接住的水画成蓝色，堆在每根柱子头顶。三个要点：
- 左右两个游标从两端往中间走，标签在基线下方两行（
L 绿色在上、R 蓝紫在下）。它们一定会越靠越近，最后一帧相遇。
- 金色外环标出"这一帧刚结算的那一格"。注意看：金环有时在左、有时在右 —— 因为算法每一轮只结算较矮的那一端。
- 顶部横幅实时显示
leftMax / rightMax 和累计水量。你会看到 rightMax 在前几轮被推高到 2 之后就不再变了 —— 因为右边那根高度 3 的柱子（下标 7）之后，右侧的最高值已经封顶。
最值得盯的一帧是第 10 帧（
l = 5 那格）：这一格一次结算了
2 单位水 —— 它是整个图里最深的一格，也是"左右最高取短板"最直观的一次。
五、完整推演表（13 帧逐帧）
输入
height = [0,1,0,2,1,0,1,3,2,1,2,1]，答案
6。
几个值得单独拎出来的观察：
帧 1 和帧 2 都没接到水：因为它们各自是"目前为止最高"的柱子 —— 自己就是边界，边界存不住水。
left_max - height[l] 恰好为
0，这就是第三节说的"先更新再结算"自动消零。
帧 5、6、7 连续结算右边三次：左端那根高度
2 的柱子（下标 3）连续三轮都比右端矮或相等，于是右边一路收缩。注意
rightMax 在帧 5 被抬到
2 之后就再也不变了。
帧 8 是一个分水岭：左指针走到下标 3（高度
2）时，
leftMax 被抬到
2，和
rightMax 打平。
从这帧起，结算的天平倒向左边 —— 后面四帧全是
settle-l，把中间那个大凹槽（下标 4、5、6）一口气填完。
帧 10 是全场最大的一笔：
l = 5（高度 0），
leftMax = 2，一次结算
2 单位 —— 正是第一节手动验证过的那格。
六、为什么"较矮的那一端"可以立刻结算
这是全篇最核心的一节。
背代码的人很多，能讲清这段的人不多 —— 而面试恰恰考这个。
先摆出困难：算法里的
left_max 是"
到目前为止见过的最高"，不是全局的"左侧最高"。扫描还没结束，右侧是什么样我们根本不知道。那凭什么敢拿这个局部值当水位？
以 height[l] < height[r]、结算左端为例。
第一步（容易看到的）：
l 的右边至少有一根高度 >= height[r] 的柱子 —— 就是 r 自己那根。
而 height[r] > height[l]，所以 l 的右侧最高一定严格大于它自己的高度。
这一步只说明"右边不会漏水"，还不够 —— 短板是
min(左, 右)，我们还得排除"左边比右边还高、右边才是短板"的情况。
第二步（真正的论证，用反证）：
假设反过来：left_max 超过了真正的右侧最高。
那么 left_max 来自 [0..l] 里的某根高柱 k。
想一想左指针经过 k 的那一刻：height[k] 比当时右边所有已扫过的柱子都高，
于是判据 height[l] < height[r] 在那里不成立，算法会转头去结算右侧；
右侧会一路收缩，直到出现一根更高的柱子（把 right_max 抬到 > left_max），或者指针相遇。
无论哪种情况，等算法真的走到 l 来结算时，右侧最高已经不可能低于 left_max 了。
所以结论是：
矮的那一端，它的"外侧上界"已经由对面的柱子保证了；对侧不可能是短板。
于是水位可以放心地用"已知的这一侧"来定 —— 这就是为什么双指针不需要预处理两个数组。
一句话记法：
谁矮结算谁，因为矮的那一侧的答案已经"单方面确定"了。
七、换个视角：单调栈，横着切
前面三种解法都是
竖着切 —— 站在位置
i 上问"我头顶能存多少水"，一次算完一整列。
单调栈是
横着切：不问每一列，而是
找到一个凹槽就结算一整层。
def trap(height):
stack = [] # 存的是下标（不是值），对应高度单调递减
ans = 0
for i in range(len(height)):
while stack and height[i] > height[stack[-1]]:
top = stack.pop() # 槽底
if not stack:
break # 只有右边界、没有左边界 → 围不出凹槽
width = i - stack[-1] - 1
bounded = min(height[i], height[stack[-1]]) - height[top]
ans += width * bounded
stack.append(i)
return ans
7.1 它在干什么
栈里存的是
还没找到右边界的、高度一路下降的那些柱子。一旦遇到一根比栈顶更高的柱子，说明凹槽的右边界出现了：
- 栈顶 = 槽底
- 弹出后的新栈顶 = 左边界
- 当前这根 = 右边界
于是这一层的水：
宽 = 右边界 - 左边界 - 1
高 = min(左边界高度, 右边界高度) - 槽底高度 ← 又是木桶原理
水量 += 宽 × 高
注意弹栈是
while —— 一根足够高的右边界会
一口气盖住好几层。
7.2 单调栈的关键帧
还是官方例
[0,1,0,2,1,0,1,3,2,1,2,1]，挑出所有"真的接到水"的帧：
看帧 13：
i = 7 那根高度
3 的柱子，一口气结算了
两层（帧 12 的
2×0 和帧 13 的
3×1）。这就是为什么弹栈要写成
while。
7.3 "按层累加"最硬的证据
对比一下两个动画里
下标 5 那格的水是怎么来的：
- 双指针（竖着切）：帧 10 一次结算完 ——
leftMax(2) - height(0) = 2，两单位一步到位。
- 单调栈（横着切）：分两次加上 ——
i = 6 时加 1 层（凹槽 [4,6]），i = 7 时再加 1 层（凹槽 [3,7]），1 + 1 = 2。
同一个位置的水，竖着切是一整笔，横着切是好几笔。 这是两种视角最直观的差别，也是"单调栈为什么能工作"的最好注脚：它算的不是"这格能存多少"，而是"这一层能铺多宽"。
两个解法的复杂度都是
O(n)：每个下标恰好入栈一次、出栈一次。区别在空间 —— 双指针
O(1)，单调栈最坏
O(n)。
八、进阶：LC 407 接雨水 II —— 当"左右"变成"四面八方"
三维版给你一个
m × n 的高度矩阵，每个格子四面都可能漏水，问总共能接多少水。
输入：heightMap = [[3,3,3,3,4],[3,2,2,3,4],[3,2,1,3,4],[4,4,4,4,4]]
输出：5
8.1 一维的公式在这里失效了
min(左最高, 右最高) 在二维没有直接对应物 —— 一个格子的"周围"不是一个方向，而是
无数条通往边界的路径。
但把这个公式
翻译一下，推广路径就自己浮现了：
一维里，leftMax[i] 是什么？是从 i 往左走到边界这条路径上，最高的那根柱子 —— 也就是这条路径的瓶颈。
rightMax[i] 同理，是"往右走"那条路径的瓶颈。
所以一维的水位 = "往左走"和"往右走"这两条路径的瓶颈，取较小者。
二维里，从格子到边界有无数条路径，水位 = 所有路径瓶颈的最小值：
水位(x, y) = min over 所有到边界的路径 p 的 ( max(height) along p )
这是图论里的"最小瓶颈路径"问题 —— 而"最小化路径上的最大值"正是 Dijkstra 的一个标准变体（把"路径权值之和最小"换成"路径最大值最小"）。
8.2 多源 Dijkstra：从边界往内灌
从每个格子出发找路径太慢；反过来想 ——
从边界出发。所有边界格子本身就是"已知的边界"，它们的水位就是自己的高度。把它们全部放进一个
最小堆，然后不断取出
水位最低的那个格子，向内扩散：
import heapq
def trapRainWater(heightMap):
m, n = len(heightMap), len(heightMap[0])
if m < 3 or n < 3:
return 0 # 没有内部格子
visited = [[False] * n for _ in range(m)]
heap = []
# ① 所有边界格子入堆：它们是初始的"围堰"，水位 = 自身高度
for i in range(m):
for j in range(n):
if i == 0 or i == m - 1 or j == 0 or j == n - 1:
visited[i][j] = True
heapq.heappush(heap, (heightMap[i][j], i, j))
ans = 0
while heap:
h, x, y = heapq.heappop(heap) # ② 当前围堰上最矮的那根
for dx, dy in ((1, 0), (-1, 0), (0, 1), (0, -1)):
nx, ny = x + dx, y + dy
if 0 <= nx < m and 0 <= ny < n and not visited[nx][ny]:
visited[nx][ny] = True
if heightMap[nx][ny] < h:
ans += h - heightMap[nx][ny] # ③ 矮于围堰 → 接水
# ④ 新围堰高度：格子高就用它自己，矮就用水位顶上来
heapq.heappush(heap, (max(heightMap[nx][ny], h), nx, ny))
return ans
三个关键点：
为什么取堆顶（水位最低）就能保证正确？ 这和一维双指针的论证
同构：当处理围堰上最矮的那根
h 时，任何还没访问的格子，它到边界的任何路径都必须经过当前围堰 —— 而围堰上最矮的就是
h，所以它的水位
至少是
h；又因为堆保证
h 是当前可能的最小瓶颈，所以水位
恰好是
h。
这就是 Dijkstra 的贪心正确性，一字不差地搬了过来。
入堆的为什么是 max(自身高度, 当前水位)？ 因为一个格子被水淹后，它对
更内部的格子而言就不再是"高度
height[x][y] 的柱子"，而是"高度为水位的围堰"。这行代码是整个算法最容易写错的地方。
为什么入堆时就标记 visited（而不是出堆时）？ 因为第一次入堆时的水位就是最终水位（堆的单调性保证），后到的路径只会更高。
这和一维的"left_max 先更新再结算"是同一个道理：第一次就是最优，之后不用再看。
复杂度：每个格子入堆出堆各一次，堆操作
O(log(mn)) —— 总计
O(mn·log(mn))，空间
O(mn)。
8.3 一张表收束全篇
一维版其实是二维版的退化特例 —— 只有两个方向的"所有路径"。而二维解法反过来也能解一维（把数组想成一列格子）。这一对题放在一起看，"木桶原理"才算真正贯通。
九、Java 版
class Solution {
public int trap(int[] height) {
int l = 0, r = height.length - 1;
int leftMax = 0, rightMax = 0, ans = 0;
while (l < r) {
if (height[l] < height[r]) {
leftMax = Math.max(leftMax, height[l]);
ans += leftMax - height[l];
l++;
} else {
rightMax = Math.max(rightMax, height[r]);
ans += rightMax - height[r];
r--;
}
}
return ans;
}
}
三维版的 Java 实现用
PriorityQueue（小根堆），结构与上面 Python 版完全一致；唯一要注意的是 Java 的
PriorityQueue 默认是
大根堆，要传
(a, b) -> a[0] - b[0] 才是小根堆 —— 这个默认值坑过不少人。
十、复杂度
双指针的
O(n) 有一个容易忽略的细节：
两个指针合计最多走 n 步，不是"每个位置都要左右夹一遍" ——
l 和
r 加起来最多覆盖整个数组一次，这就是内层无循环的底气。
十一、边界情况与常见坑
边界情况
常见坑
坑 1：left_max 先结算再更新
新高那格会算出
负数，把总量往回扣。正确顺序永远是"先更新、再结算"，让新高自动消零。
坑 2：双指针的判据写反
height[l] < height[r] 时结算
左端。写反的话，你会去结算较高的一端 —— 而那一端的外侧上界还没确定，答案会
偏大（把不该存的水也算进去了）。这类 bug 官方样例
测不出来：
[0,1,0,2,1,0,1,3,2,1,2,1] 两端恰好相差
1，两种判据都能得到
6。要测就用
[5,0,1]（正确
1，判据写反会得
4）或
[4,0,0,0,3]（正确
9，写反会得
12）。
坑 3：单调栈弹栈后不检查栈空
top = stack.pop()
if not stack:
break # ← 漏掉这行，下面 stack[-1] 会越界
弹出后栈空说明
只有右边界（弹出的就是当前最左的柱子），左边没有墙，围不出凹槽。
坑 4：单调栈的栈存了"值"而不是"下标"
宽度公式
i - stack[-1] - 1 需要的是
下标。存值的话宽度算不出来，只能另开一个平行数组记下标，反而更绕。
坑 5：三维版入堆时忘了 max(自身高度, 水位)
直接入堆
heightMap[nx][ny] 的话，一个被水淹过的洼地会以"干地"的身份参与后续围堰，内部的水位会被低估。
一格被淹之后，它对更内部的格子而言就是"水位那么高的墙"。
坑 6：三维版忘了处理 m < 3 或 n < 3
行数或列数不足
3 时
没有内部格子，直接返回
0。不写这个守卫，边界初始化的循环会照常跑，虽然大多数时候答案恰好也是
0，但逻辑上是在"用没有内部格子的流程接水"，纯属侥幸。
十二、面试怎么答
接雨水是"三种解法层层递进"的标准素材，建议的答法顺序：
-
先给核心公式："
water[i] = max(0, min(左最高, 右最高) - height[i])，木桶原理。整道题只是在问'每个位置的两侧最高是多少'。"
-
说暴力与 DP："暴力每个位置扫两边，
O(n²)；发现'往左扫'可以复用，就预处理两个数组，O(n) 时间 O(n) 空间。"
-
引出双指针并讲清论证（这段是分水岭）："双指针把预处理变成边走边算，关键在为什么敢用局部最大值结算 —— 因为较矮的那一端，它的外侧上界已经由对面的柱子保证了；对侧不可能是短板。反证：如果左侧那根高柱真是更高的那个，它当年经过时判据就不会选它，右侧会被一路收缩到出现更高的柱子为止。"
-
主动补单调栈："还有一个横着切的视角：栈里维护高度递减的下标，遇到更高的柱子就结算一层。它和双指针的答案一致，但同一个位置的水会被分几次加上 —— 这是两种视角最直观的差别。"
-
如果面试官追问三维版："把
min(左最高, 右最高) 翻译成'两条路径瓶颈取 min'，二维就是'所有路径瓶颈取 min' —— 最小瓶颈路径，多源 Dijkstra，从边界入最小堆，每次取水位最低的向外扩散。复杂度 O(mn·log(mn))。"
结语
接雨水这道题最迷人的地方，是它把"一个问题"换了好几副面孔：
- 暴力和 DP 说：把每个位置的两侧最高都算出来。
- 双指针说：不需要全部算出来，只算"已经确定的那一半"。
- 单调栈说：别按列算了，按层填 —— 同一格的水可以分几次到账。
- 而三维版说："左右最高"本来就只是"路径瓶颈"的特例，把两个方向推广到所有方向，接雨水就变成了 Dijkstra。
四副面孔背后是同一个木桶原理：
水停在短板上。一维的短板是两根柱子里较矮的，二维的短板是所有路径里最平缓的那条。
最后自测一下 —— 特别是用
示例 2，因为它的水更深、更容易暴露判据写反的 bug：
assert trap([0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1]) == 6 # 官方例 1
assert trap([4, 2, 0, 3, 2, 5]) == 9 # 官方例 2
assert trap([5, 0, 1]) == 1 # 判据写反会得 4
assert trap([4, 0, 0, 0, 3]) == 9 # 判据写反会得 12
assert trap([2, 0, 2]) == 2 # 最小的凹槽
这几行比跑十遍官方样例有用。