先说个我自己的经历。第一次刷到 LeetCode 407 接雨水 II 的时候我在草稿纸上画了半小时的方格图试着把一维接雨水那套左右两边最高墙取较小值的逻辑硬塞进去结果怎么改都过不了。后来才想明白这题的难点压根不在代码而在于你能不能转过水只能从地图边界流出去这个弯。想通之后代码不到三十行写起来甚至比一维版本还顺手——这也是标题里说它超级简单易懂的底气前提是你得先把脑子换过来。这篇东西我打算把 407 从头到尾拆一遍一维接雨水的结论为什么在二维直接失效、优先队列配合边界收缩的思路是从哪冒出来的、堆里那个 max 操作到底在防什么、Python 和 Java 以及 C 三份代码各自有哪些坑、面试官顺着这道题往下追会问什么。不管你是刚打开 leetcode 热门 100 题榜单的新手还是写过三五遍每回都要重新推一遍的老手应该都能从里面抠出点东西。整篇不玩虚的所有推理过程我都尽量摊开写代码给全能直接提交。1. 一维接雨水的结论搬到二维为什么直接失效1.1 一维版本的核心其实就一句话一维接雨水那道经典题结论浓缩起来就是每个位置能蓄多少水取决于它左边最高的那根柱子和右边最高的那根柱子两者中较矮的那个决定了天花板再减掉自己脚下这块地的高度。写成公式就是water[i] max(0, min(leftMax[i], rightMax[i]) - height[i])。这个式子的物理含义特别直白水往低处流但流到一半被两边的墙夹住了它能蓄多高由两边墙里矮的那一边说了算。就像你拿一个盆接水盆沿一边高一边低水一定从矮的那边溢出去所以水面永远停在矮沿的高度上。理解了这个木桶效应一维版本无论是暴力预处理前缀最大值还是用双指针把空间压到 O(1)都只是实现技巧上的差别思路内核是一模一样的。双指针的优化为什么能成立本质上是因为我们每次只从较矮的那一侧结算当左指针位置的柱子比右指针位置的柱子矮时右侧一定存在一根不低于它的柱子于是左指针这个位置的天花板就只由它左边已知的最高墙决定可以放心结算然后左指针右移。整个过程没有回头路一遍扫完O(n) 时间 O(1) 空间干净利落。这个从确定的一侧往里收缩的直觉等下会以另一种形式出现在 407 里。1.2 二维世界里左右两边不再是一条线问题来了到了二维网格每个格子不再只有左右两个方向而是上下左右四个方向甚至可以说存在无穷多条通往边界的路径。你没办法用两个变量概括左边最高和右边最高因为左边到底是贴着同一行往左走还是可以拐弯绕行这个歧义直接让一维公式破产。更要命的是二维里的水不一定沿着你眼睛看到的最短直线流走。假设某个低洼格子的正上方是一堵高墙但斜上方的远处有个缺口水照样能绕过那堵墙从缺口流出去。所以你不能再盯着一个方向的墙体算账而要考虑这个格子里的水最终能从哪里逃出去。换个角度把问题重新描述一遍对任意一个内部格子从它出发向任意方向走到地图边界会形成无数条路径每条路径上都有一个最高的格子可以理解成这条路线的瓶颈高度那么真正决定这个格子水位上限的是所有路径中最小的那个瓶颈值。因为水流一定会走对它最有利的那条路也就是翻越最矮的那个关口。这个值在算法圈有个正经名字叫最小化路径最大值的路径问题或者叫最小瓶颈路。1.3 用一句话重新定义 407 的答案有了上面的铺垫407 的答案就可以非常精确地写出来了对每个格子 (i, j)计算从它出发到边界的全部路径中「路径上最大高度」的最小值记作cap这个格子实际的蓄水量就是max(0, cap - height[i][j])。把全部格子的蓄水量加起来就是最终答案。这里有两个细节必须拎清楚。第一路径是包含起点本身的所以如果这个格子自己就很高比如是整片区域的最高点那它出发的每条路径的最大值都至少等于它自己cap就等于它自己的高度蓄水量为 0正好符合常识。第二边界上的格子不需要计算它们的水直接就流走了蓄水量天然为 0所以它们正好可以当作整个算法的起始点。把这句话翻译成工程实现就引出了下一节的主角最小堆加边界收缩。2. 核心算法选型为什么是优先队列配边界收缩2.1 水桶模型给出的直觉我特别喜欢用一个慢慢注水的桶来理解这题。把所有边界格子想象成围成一圈的桶壁每块壁的高度各不相同。现在往桶里倒水水会从最矮的那块壁溢出去所以无论桶内多低水面都不会超过这块最矮的壁。于是我们先把所有边界格子丢进一个最小堆堆顶就是当前最矮的那块桶壁。取出它看看它周围的邻居格子如果某个邻居比它矮那水就能在这个邻居上方蓄起来水面高度就是这个桶壁的高度如果邻居比它高那这个邻居自己就变成了更高的一块新桶壁不蓄水。接下来是最关键的一步无论邻居是矮是高我们都把max(桶壁高度, 邻居自身高度)这个值作为邻居的有效高度重新放回堆里。腾出来之后这块新位置就变成了下一轮的外圈可以继续向内推进。你会发现整个过程就像一圈圈围墙不断向内收缩而堆始终保证我们每次处理的是当前轮廓线上最矮的那一格。2.2 堆里存 max 而不是存原高度到底在防什么很多人第一次写这题会顺手写成heap.push(邻居自身高度)然后发现结果偏小。原因很简单邻居这块地在自己不蓄水的同时还承担了给更内圈格子当围墙的职责。如果只把它的原始高度塞回去那么它就会以一个偏低的身份参与后面的比较导致更内圈的格子被误认为天花板很低。举个例子外圈高度是 10紧挨着的一格高度是 3再往里一格高度是 1。处理到高度 3 这一格时水面定在 10积水 7同时它作为一道墙它的实际有效高度是 10 而不是 3。如果堆里存的是 3那么当这格向外扩展碰到高度 1 的格子时就会误判水位是 3积水 2而正确答案是水位 10、积水 9。差了一大截。用max(当前水面高度, 邻居自身高度)就解决了这个问题它能保证堆里的每一个元素代表的都是从这个位置往外能挡住水的下限高度。这个不变式一旦成立整个算法的正确性就稳了。2.3 普通 BFS 或者 DFS 为什么一定会翻车有人会想那我从边界开始做个普通 BFS 不就行了广度优先遍历整个网格每次记录访问路径上的最大值。问题在于BFS 是按距离层次推进的它先看到的路径不一定是最优路径。假设某个格子有两条通往边界的路线一条很近但要翻过一堵高墙一条很远但全程都很低。BFS 会优先走那条近路把水位算高等它发现远路时格子已经被标记访问过了不会重新计算。结果就是答案偏大。DFS 就更随意了访问顺序取决于你写循环的方向换一个方向顺序结果可能就变了。这类问题的本质是你需要按瓶颈值从小到大的顺序处理节点而不是按距离顺序。这正好是 Dijkstra 的思路而 Dijkstra 的标准实现载体就是优先队列最小堆。所以堆不是可选项而是刚需。2.4 复杂度算清楚心里才有底每个格子最多入堆一次、出堆一次堆的规模最大是 m×n单次操作是 O(log(mn))所以总时间复杂度 O(mn log(mn))。空间方面visited 数组占 O(mn)堆最多同时装着轮廓线上的格子最坏情况也是 O(mn)。在题目给的 200×200 规模下也就是四万个格子四万次堆操作任何主流语言都能轻松跑进时限。顺便说一句这题还有别的做法。比如二分答案二分一个水位高度然后做一次 BFS 判断水能不能漫过这个高度复杂度 O(mn log(maxH))也能过但代码量翻倍而且容易在边界判断上出错。还有用并查集的把格子按高度从小到大排序后逐个合并本质是 Kruskal 求最小生成树写起来更绕。我个人的建议是刷题阶段就死磕堆这一种把它吃透比记三种半懂不懂的解法有用得多。对比维度一维接雨水二维接雨水 II水位决定因素左右最高墙取较小到边界所有路径瓶颈值的最小值主流实现双指针 / 单调栈最小堆 边界向内收缩时间复杂度O(n)O(mn log(mn))空间复杂度O(1) 或 O(n)O(mn)核心直觉木桶短板逐圈注水从最低处溢出3. 三份可直接提交的代码附带逐行拆解3.1 Python 版本十七行搞定import heapq class Solution: def trapRainWater(self, heightMap): if not heightMap or not heightMap[0]: return 0 m, n len(heightMap), len(heightMap[0]) if m 3 or n 3: return 0 visited [[False] * n for _ in range(m)] heap [] # 1. 把所有边界格子作为初始轮廓线入堆 for i in range(m): for j in range(n): if i 0 or i m - 1 or j 0 or j n - 1: heapq.heappush(heap, (heightMap[i][j], i, j)) visited[i][j] True ans 0 dirs ((-1, 0), (1, 0), (0, -1), (0, 1)) # 2. 反复取出当前轮廓线上最矮的格子向内扩展 while heap: h, i, j heapq.heappop(heap) for di, dj in dirs: ni, nj i di, j dj if 0 ni m and 0 nj n and not visited[ni][nj]: visited[ni][nj] True # 入堆前就标记 ans max(0, h - heightMap[ni][nj]) heapq.heappush(heap, (max(h, heightMap[ni][nj]), ni, nj)) return ans逐行说一说。开头两行判空很多人会忽略其实是保命代码尤其是面试手写时不给测例的情况。m 3 or n 3这个提前返回也很关键如果网格只有一行或者一列那所有格子都在边界上压根存不住水直接返回 0同时也避免了后面循环里出现没有内部格子的尴尬。初始化的双重循环把四条边上的格子全部入堆并标记已访问。这里用已访问而不是未访问是因为边界本来就存不住水把它当作已经处理过的外圈来处理逻辑上更干净。主循环里有两处细节值得反复看一是visited[ni][nj] True写在入堆之前而不是弹出之后。如果你习惯性地在弹出时才标记那同一个格子可能被四个邻居分别入堆一次答案会重复累加堆的规模也会膨胀。二是ans max(0, h - heightMap[ni][nj])里的max(0, ...)不能省当邻居比当前水面还高时差值是负数不加保护就会把总答案往下拉。虽然那种情况下我们随后会用max修正入堆高度但答案累加这一步必须先夹住。3.2 Java 版本比较器和装箱的坑class Solution { public int trapRainWater(int[][] heightMap) { if (heightMap null || heightMap.length 0 || heightMap[0].length 0) return 0; int m heightMap.length, n heightMap[0].length; if (m 3 || n 3) return 0; boolean[][] visited new boolean[m][n]; // 小根堆按高度升序高度相同时任意 PriorityQueueint[] pq new PriorityQueue((a, b) - a[0] - b[0]); for (int i 0; i m; i) { for (int j 0; j n; j) { if (i 0 || i m - 1 || j 0 || j n - 1) { pq.offer(new int[]{heightMap[i][j], i, j}); visited[i][j] true; } } } int ans 0; int[][] dirs {{-1, 0}, {1, 0}, {0, -1}, {0, 1}}; while (!pq.isEmpty()) { int[] cur pq.poll(); int h cur[0], i cur[1], j cur[2]; for (int[] d : dirs) { int ni i d[0], nj j d[1]; if (ni 0 || ni m || nj 0 || nj n || visited[ni][nj]) continue; visited[ni][nj] true; ans Math.max(0, h - heightMap[ni][nj]); pq.offer(new int[]{Math.max(h, heightMap[ni][nj]), ni, nj}); } } return ans; } }Java 这边最大的坑是PriorityQueue的默认行为。它默认是小根堆没错但它要求元素可比较而int[]数组本身没有实现Comparable你不写比较器编译能过运行时抛ClassCastException。比较器写成(a, b) - a[0] - b[0]就够了因为高度范围在 20000 以内相减不会溢出 int。另一个常见疑问是能不能用(a, b) - Integer.compare(a[0], b[0])当然可以风格上更稳妥防止将来数值范围变大导致相减溢出。刷题时两种写法都行工程代码里我建议用后一种。还有个小细节visited[ni][nj] true和ans累加的顺序跟 Python 版保持一致就好。顺序本身不影响正确性因为这两个操作没有依赖关系但保持统一风格能让你在两种语言之间切换时少犯错。3.3 C 版本结构化绑定的版本要求class Solution { public: int trapRainWater(vectorvectorint heightMap) { if (heightMap.empty() || heightMap[0].empty()) return 0; int m heightMap.size(), n heightMap[0].size(); if (m 3 || n 3) return 0; vectorvectorbool visited(m, vectorbool(n, false)); // 小根堆tuple 默认按字典序比较正好等价于按高度排序 priority_queuetupleint,int,int, vectortupleint,int,int, greater pq; for (int i 0; i m; i) for (int j 0; j n; j) if (i 0 || i m - 1 || j 0 || j n - 1) { pq.emplace(heightMap[i][j], i, j); visited[i][j] true; } long long ans 0; int dirs[4][2] {{-1,0}, {1,0}, {0,-1}, {0,1}}; while (!pq.empty()) { auto [h, i, j] pq.top(); pq.pop(); for (auto d : dirs) { int ni i d[0], nj j d[1]; if (ni 0 || ni m || nj 0 || nj n || visited[ni][nj]) continue; visited[ni][nj] true; ans max(0, h - heightMap[ni][nj]); pq.emplace(max(h, heightMap[ni][nj]), ni, nj); } } return (int)ans; } };C 这边用tuple配合greater是个偷懒又正确的写法因为 tuple 的比较规则是先比第一个元素相等再比第二个以此类推而我们正好希望按高度排序。要注意的是auto [h, i, j] ...这种结构化绑定需要 C17 标准如果评测环境只支持 C14改成tupleint,int,int cur pq.top(); int h get0(cur);就行了。这里我特意把ans声明成long long。虽然按题目约束算下来最大值不会超过 int 范围但在工程习惯上凡是累加类变量我都倾向于用宽类型出问题的时候排查成本远高于多占那几个字节。最后返回时强转回 int 即可。三份代码的逻辑完全一致挑一门你刷题常用的语言抄进编辑器跑一遍再自己默写两遍这道题基本就刻进肌肉记忆里了。3.4 跟着堆走一遍看看水位是怎么被抬上去的光看代码容易晕我们拿一个小网格手动跑一遍。假设地图是这样2 2 2 2 2 2 9 9 9 2 2 9 1 9 2 2 9 9 9 2 2 2 2 2 2这是 5×5 的格子外圈全是 2中间一圈是 9正中心是 1。很明显中心那个 1 想往外流必须翻过一圈高度 9 的墙所以水位会被顶到 9蓄水量是 8。算法能不能自动得出这个结果能。第一步把最外圈的 16 个高度为 2 的格子全部入堆。堆顶是 2弹出来检查它的四个邻居。最外圈格子的邻居里有一部分还是外圈已访问有一部分是内圈的 9。第二步这些 9 被首次访问max(0, 2 - 9)得到 0不蓄水但它们入堆的高度是max(2, 9) 9。所以堆里现在混着高度 2 和高度 9 的元素堆顶依然是 2。第三步继续弹出所有高度 2 的元素它们能扩展到的内圈 9 已经全部标记过了没有新的格子被发现。这时候堆顶就变成了 9。第四步弹出高度 9 的格子它的邻居里有正中心那个高度 1 的格子未被访问。ans max(0, 9 - 1) 8然后把max(9, 1) 9入堆。中心格子处理完堆里剩下的元素都扩展不出新格子循环结束。最终答案就是 8。你注意第四步里水位是 9 而不是 2——虽然外圈更矮但水要先漫过内圈那堵 9 的墙才能出去所以真正的天花板是 9。这个例子最好地说明了为什么必须用堆如果按 BFS 的层次顺序走很可能先从外圈的 2 开始就误判水位。4. 常见问题与排查技巧实录4.1 结果偏小八成是丢了 max前面提过一次但值得再强调pq.offer(new int[]{Math.max(h, heightMap[ni][nj]), ni, nj})里的Math.max是最容易被漏掉的地方。漏了它所有新扩展出来的格子都会以自身原始高度进入堆导致更内层的格子被低估。这个 bug 的隐蔽之处在于简单的测例比如外圈 3、内圈 0 那种跑出来是对的只有遇到中间夹一层矮格子的结构才会暴露。我自己的排查办法是构造三组数据打桩。第一组是全平的网格答案必然是 0用来验证不误报。第二组是经典例题答案已知是 4。第三组就是上面那个外 2 内 9 心 1的构造答案必须是 8。三组都过基本就稳了。4.2 结果偏大检查 visited 标记时机如果答案莫名其妙偏大十有八九是visited标记写在弹出的时候而不是入堆的时候。这样一来一个格子会被它的多个邻居分别入堆弹出时就会被累加多次。举个直观的场景某个低洼格子有上下左右四个邻居如果都在它被弹出之前把它入堆那它就会在堆里出现四次每次弹出都会加一遍积水。判断方法也很简单在循环里加一句打印看看同一个坐标有没有被处理超过一次。有就是标记时机的问题。4.3 数组越界和空输入的防守题目虽然保证了输入是合法矩阵但手写代码的时候该有的判断还得有。heightMap null || heightMap.length 0 || heightMap[0].length 0这三连是标配。另外if (m 3 || n 3) return 0;这一句既优化了性能又顺手规避了内部没有可蓄水格子的边界情况。有些实现忘了这一句虽然主循环也不会出错但白跑一遍 O(mn) 的入堆逻辑属于无谓开销。现象最可能的原因修复方式结果偏小入堆时未取 max写成 max(水面高度, 邻居高度)结果偏大visited 在弹出时才标记改为入堆前立即标记结果偶发偏大累加时未做 max(0, ...) 保护差值取非负运行时异常Java 未给数组写比较器补上按首元素升序的比较器编译不过C 用了 C17 的结构化绑定改为 get0 取值或升标准一行或一列的输入未提前返回加 m 3 或 n 3 的判断4.4 三维延伸其实也难不倒你有人在评论区问过如果地图变成三维立方体怎么办。答案是这个算法一个字都不用改只是方向数组从 4 个变成 6 个上下左右前后初始轮廓从四条边变成六个面。本质逻辑完全一样所有表面格子入堆每次弹出最矮的向内推一层新格子的高度取 max。想清楚这一点说明你对这套模型是真的理解了而不是背下来的。5. 把 407 抽象成一个通用模型5.1 最小瓶颈路这个模型的应用范围比你想的广407 的底层数学结构叫最小瓶颈路问题。它的标准定义是在带权图里从起点到终点有若干条路径每条路径的权重定义为路径上最大边的权值求所有路径中这个最大边权的最小值。求解它的经典手段有两个一个是优先队列版的 Dijkstra 变体另一个是构造最小生成树——因为有一条很漂亮的定理任意两点间的最小瓶颈路一定落在最小生成树上。放到 407 里每条边的权重就是格子的高度路径权重就是路径上最高格子的高度。求的正是中心格子到边界的最小瓶颈值。理解了这层抽象你会发现同类题目其实是一整个家族。5.2 同源题目一网打尽LeetCode 778 水位上升的游泳池问的是从左上角走到右下角路径上最大值的最小值是多少这就是最小瓶颈路的标准形态可以用二分加 BFS 做也可以直接堆 Dijkstra。1631 最小体力消耗路径把路径权重从最大值换成了相邻差值的最大值结构一模一样只是比较的对象从节点值变成了边的差值。再往远一点说网络路由里找一条最不拥堵的路径、电路布线里找一条最不容易烧断的线路都是同一类问题的变体。所以刷这道题的时候别只想着把它 AC 掉多花十分钟把什么时候该用堆这个判断条件想明白收益会大得多。5.3 面试官顺着这题往下追通常会问什么第一问大概率是为什么用优先队列普通队列行不行。这时候你要答的是顺序性必须按瓶颈值从小到大处理才能保证第一次访问某个格子时用的就是最优路径这跟 Dijkstra 的贪心正确性是一回事。第二问可能是时间复杂度还能不能降。答案是标准解法就是 O(mn log(mn))除非牺牲通用性。二分的做法是 O(mn log(maxH))理论上跟堆版本同阶但常数更大。第三问可能是如果要求返回所有蓄水格子的坐标和水量而不是总和呢。改法很简单把ans ...换成往结果列表里塞一个三元组同时把每个格子的最终水位记录下来不需要动主干逻辑。第四问有时候会拐到并查集上能不能用并查集从外向内合并。可以思路是把格子按高度排序从小到大依次加入用一个虚拟的外部节点表示边界当某个格子与外部连通时它就存不住水了。但代码复杂度明显上升面试里除非被点名要求不建议主动往这条路上走。6. 刷完这道题之后我攒下的几点真实体会第一点这类网格 瓶颈路径的题目判断该不该用堆有一个很好用的信号当你发现某个位置的答案只取决于一条路径上的最值而不是路径长度或者路径总和时基本上就是堆的活。反过来如果答案跟路径长度有关那就是普通 BFS跟路径总和有关那就是 Dijkstra 的最短路径版本。三种信号对应三种工具分清楚了看图论题就不会再靠猜。第二点我踩过最深的坑不是算法本身而是代码里的顺序。visited什么时候标记、max什么时候取、ans什么时候累加这三件事每换一种语言写都容易错位一次。后来我给自己定了个规矩不管写哪个语言都先把这三行按固定顺序摆好再填内容。养成这个习惯之后一次性通过率明显上去了。第三点关于验证。我强烈建议你自己手写一个暴力版本用来对拍。暴力版本的写法是对每个内部格子做一次广度优先搜索用小根堆维护从它出发到边界的最小瓶颈值把每个格子的结果算出来最后加总。虽然它是 O((mn)^2 log(mn))跑不了大数据但用来验证小规模随机数据足够了。随机生成 5×5 到 8×8 的网格跑一百组对拍如果结果全都一致那你这道题算是真正拿下了。第四点讲讲心态。407 在 leetcode 热门 100 题里算偏难的一道第一遍做不出来太正常了。我建议的做法是先自己硬想四十分钟想不出来再去看提示只看到优先队列这个关键词就停剩下的自己补。这样既保留了思考的价值又不会卡死在一道题上消耗热情。毕竟刷题的节奏感比单题的胜负重要得多。