接雨水这三个字在算法圈里算是个老熟人了。一维版本42 题用双指针二十分钟就能写完很多人刷完之后信心爆棚顺手点开 leetcode 407. 接雨水II然后发现自己的双指针思路在这里彻底失效——左右两边的最高柱子突然变成了四面八方的通道一维里那个左右取较小值的优美结论直接蒸发。如果你正在按一份 leetcode 刷题指南往下推或者刚打完 leetcode 周赛430 想找道困难题练手407 是个绕不开的坎。它的难点不在代码长度而在于你得先想清楚二维世界里水到底怎么流出去这件事。这篇内容我会把 407 的解题路径从为什么双指针不行一路讲到最小堆加广搜的不变量,再补一个用并查集求最小瓶颈路径的进阶视角,顺带把我自己在实现过程中踩过的坑逐个摆出来。适合已经会写 42 题、但被二维版本卡住的人,也适合想把优先队列类 BFS 模板吃透的读者。1. 二维接雨水到底难在哪先把水位这两个字定义清楚很多人做 407 卡壳不是因为不会写优先队列而是因为脑子里对水位这个概念只有一维版本的模糊印象。一维里水位很好理解某个位置上方能积多少水取决于它左边最高柱子和右边最高柱子中较矮的那个。这个结论太顺口了以至于大家会下意识地把它当成水位的定义而不是一个一维特例下的推论。1.1 从两侧最值到全路径瓶颈一维结论为什么不能直接搬一维的情况之所以能简化成左右取较小值,是因为水只能沿两个方向流动,一个位置的水要想流到边界,路径是唯一的——要么往左走,要么往右走。所以它的水位就是两条路径瓶颈值的较小者。到了二维,一个点通往外部世界的路径数量是随网格规模指数级增长的,你没法再用两个方向去概括。真正成立的定义只有一个某个格子的水位,等于它到矩阵外部所有路径中,路径上最大高度这一指标的最小值。换个说法,把每条路径的通行难度定义为这条路上最高的那根柱子,那么水位就是所有路径里难度最低的那条。这个定义在数学上叫最小瓶颈路径,它同时是 42 题和 407 题的统一形式——回头去看 42 题,你会发现它就是一维网格上的最小瓶颈路径问题。1.2 一个公式把二维接雨水的所有版本串起来把所有东西写成一个式子,思路会清晰很多。设h(i, j)是格子高度,w(i, j)是该格子的水位,那么w(i, j) min { max h(c) | c 属于某条从 (i, j) 通往矩阵外的路径 P } 存水量 Σ max(0, w(i, j) - h(i, j))注意两个立刻能推出来的结论。第一,w(i, j) h(i, j)恒成立,因为任何从(i, j)出发的路径都包含它自己,瓶颈值不可能低于自身高度。第二,边界格子到外部只需要走它自己这一步,所以边界格子的水位恒等于它自己的高度,存水量必然是 0。这两条看似平淡,实际上是后面算法能够成立的全部基础。我见过不少人卡在这里,是因为他们想找一个幂等的推导规则,比如每个格子的水位等于四周格子水位的某种组合。这条路走不通,因为水位是全局性质,取决于整个地形的连通结构,不能只靠局部信息递归出来。1.3 边界不只是排水口,它还是算法的种子既然水最终都是从某个边界缺口流出去的,那么边界就是这个问题的天然锚点。你可以反过来理解整个算法既然边界格子的水位是已知的就是它自己的高度,那么紧挨着边界的格子,它的水位一定不超过这个边界格子的高度和它自己高度的较大值——因为水往那边流就行。这就是一个从已知推向未知的过程,和 Dijkstra 从源点向外扩散的形式完全一致。只不过在标准最短路里,我们扩展的是距离最小的点;在这里,我们要扩展的是水位最小的点。这就是为什么最小堆会登场,也是下一章要展开的核心。2. 最小堆加广搜把已经确定的水位当成围墙往外推想把最小堆版本的思路一劳永逸地记住,你只需要在心里装下一个物理画面水从矩阵外面往里漫。外面那一圈是水位已知的边界,随着水往内部推进,碰到低洼的地方就积起来,碰到高地就被挡住绕开。2.1 核心不变量堆里装的永远是当前水位最低的候选点算法的骨架分三步。第一步,把所有边界格子塞进一个小顶堆,堆里存的是三元组(当前水位, 行, 列),并且立即把它们标记为已访问。第二步,循环从堆顶取出水位最低的那个点,它就是这一轮水位已经彻底确定的点。第三步,遍历它的四个邻居,对每个没访问过的邻居,计算邻居水位 max(当前点水位, 邻居自身高度),这个值就是邻居的水位;如果邻居自身高度小于当前点水位,差值就是能存的水量,累加到答案里。然后把邻居带着它的水位入堆,并立刻标记已访问。整个算法的灵魂在于一句话从小顶堆里弹出来的点,它的水位一定已经确定了,不会再被后面出现的任何路径降低。为什么会这样因为水要给某个点解套,必须存在一条完全由比当前水位更低的水位组成的通路走到外面;而堆里剩下的所有候选点,水位都大于等于当前弹出的值,这条路根本不存在。这是一个标准的切分性质,和 Dijkstra 里弹出的点距离已定型是同一个论证。2.2 手推一个 5x5 的样例,把每一步都摊开看光说结论容易飘,拿个具体例子走一遍。假设地形是这样5 5 5 5 5 5 1 1 1 5 5 1 9 1 5 5 1 1 1 5 5 5 5 5 5外面一圈全是高度 5 的墙,里面八个格子高度是 1,正中间有个高度 9 的柱子。直觉上外围一圈的水位应该是 5,那八个低洼格子各存 4 单位水,中间那根高柱不存水,答案应该是 32。按算法走一遍。初始把 16 个边界格子全部入堆,水位全是 5,全部标记已访问。堆顶弹出(5, 0, 0),它的邻居(0, 1)和(1, 0)都已经访问过,跳过。就这样依次弹出边界点,直到弹出到(5, 0, 1)时,邻居(1, 1)还没访问。这时计算邻居高度是 1,当前水位是 5,邻居水位取max(5, 1) 5,同时5 - 1 4累加到答案,把(5, 1, 1)入堆并标记访问。继续这个过程,每当堆顶弹出的是某一圈边界上的点,就会往内推进一格。八个高度为 1 的格子各贡献 4,总共 32。等堆顶轮到中心(2, 2)时,它的邻居已经全部访问过,直接跳过。最后堆空,返回 32。整个过程中,那根 9 高的柱子从来没影响过别人的水位,因为它从一开始就没被当成围墙用——它自己入堆时水位是max(5, 9) 9,比周围的 5 还高,弹出来的时候邻居早处理完了。2.3 为什么必须是小顶堆,大顶堆和普通队列错在哪如果你把堆换成大顶堆,弹出的会是当前水位最高的点。假设先弹出的是那根高 9 的柱子,那么它往内扩展的时候会带着 9 这个水位,把本来只该存 4 的水位抬到了 9,答案直接偏大,而且偏得很离谱。大顶堆错在违背了由已知推未知必须从最小的已知值开始这个前提——高水位点能给出的是一个上界,不是确定值,只有最小的那个候选才是确定的。换成普通 FIFO 队列呢它会按照入队顺序处理,水位高的点可能先于水位低的点被扩展,同样会把上界当成确定值往下传。这个错误在小样例上经常表现不出来,因为你手写的测试用例往往地形简单、水位高低顺序恰好和入队顺序一致。这也是为什么很多人本地跑通了,一提交就错——后面第 4 章我会专门讲怎么构造能暴露这个问题的对拍样例。还有个细节容易被忽略入堆的元素应该带上水位而不是原始高度。我们从堆顶弹出的h,从头到尾扮演的都是水位这个角色,不是那个格子的地形高度。如果你在某一处把heightMap[nx][ny]和h搞混,行为会变得非常隐晦。3. 三份可以直接提交的代码,以及它们各自的写法差异思路讲完了,把代码落地。三种主流语言的写法我都给一份,顺便说说每个语言在实现时最容易出问题的细节。这三份代码逻辑完全一致,可以直接拿去提交。3.1 Python 版本用 heapq 最省事,但要记住它是小顶堆import heapq class Solution: def trapRainWater(self, heightMap) - int: m, n len(heightMap), len(heightMap[0]) # 行列不足 3 时,所有格子都在边界上,一滴水也存不住 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: heapq.heappush(heap, (heightMap[i][j], i, j)) visited[i][j] True # 注意入堆时就要标记 ans 0 dirs ((1, 0), (-1, 0), (0, 1), (0, -1)) while heap: h, x, y heapq.heappop(heap) for dx, dy in dirs: 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(h, heightMap[nx][ny]), nx, ny)) return ansPython 里heapq本身就是小顶堆,不需要额外传比较器,这一点比 Java 舒服。真正要盯住的是两处一是visited必须在入堆的瞬间就置为True,不能等到出堆;二是heappush的第一个参数必须是max(h, heightMap[nx][ny])。这两处我在第 4 章会展开讲。3.2 Java 版本比较器和溢出风险class Solution { public int trapRainWater(int[][] heightMap) { 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) - Integer.compare(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], x cur[1], y cur[2]; for (int[] d : dirs) { int nx x d[0], ny y d[1]; if (nx 0 || nx m || ny 0 || ny n || visited[nx][ny]) continue; visited[nx][ny] true; if (heightMap[nx][ny] h) ans h - heightMap[nx][ny]; pq.offer(new int[]{Math.max(h, heightMap[nx][ny]), nx, ny}); } } return ans; } }写比较器的时候,很多人习惯写成(a, b) - a[0] - b[0]。在 407 这道题里它不会溢出,因为高度上限是两万,差值远在 int 范围内;但养成用Integer.compare的习惯没坏处,换个数据范围大的题就要吃亏了。另外int[]作为堆元素虽然方便,但每次offer都要新建对象,在 200x200 的规模下会创建大约四万个数组,GC 压力不算小。如果追求极致,可以把三元组编码成一个long再入堆,用位运算拆回来。3.3 C 版本tuple 加结构化绑定的写法最干净class Solution { public: int trapRainWater(vectorvectorint heightMap) { int m heightMap.size(), n heightMap[0].size(); if (m 3 || n 3) return 0; vectorvectorbool visited(m, vectorbool(n, false)); // 小顶堆greater 让 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; } } } int ans 0; int dirs[4][2] {{1, 0}, {-1, 0}, {0, 1}, {0, -1}}; while (!pq.empty()) { auto [h, x, y] pq.top(); pq.pop(); for (auto d : dirs) { int nx x d[0], ny y d[1]; if (nx 0 || nx m || ny 0 || ny n || visited[nx][ny]) continue; visited[nx][ny] true; if (heightMap[nx][ny] h) ans h - heightMap[nx][ny]; pq.emplace(max(h, heightMap[nx][ny]), nx, ny); } } return ans; } };greater加结构化绑定这套组合在 C17 之后才完整可用,老编译器上你可能得写std::get0(cur)。另外auto [h, x, y] pq.top();一定要紧跟着pq.pop(),如果写成引用绑定,弹出之后引用就悬空了,那种崩溃现场相当难查。4. 我在 407 上踩过的坑,以及每一个坑的完整排查链路这部分是我最想写的。网上大部分题解只给最终代码,但是别人花一晚上踩的坑,你未必能靠看代码避开。我把自己的弯路按时间顺序摊开,你能看到一个错误的思路是怎么被一步步证伪的。4.1 第一次尝试把 42 题的双指针硬套过来我最初的思路非常自然既然一维是看左右两边的最值,那二维就分别看上下左右四个方向的前缀最大值,取四者中的最小值当水位。写出来大概三十行,跑官方第一个样例[[1,4,7,8,5],[2,3,5,7,1],[1,5,3,5,6],[1,2,4,2,3]],输出 5,对了。当时我还挺得意。然后我随手构造了一个反例3 3 3 3 3 3 1 9 1 3 3 3 3 3 3按四方向取最小的逻辑,(1, 2)这个高度为 9 的格子,它上下左右的前缀最大值分别是 3、3、3、3,最小值 3,于是水位 3,存水 0,看起来没问题。但(1, 1)这个高度 1 的格子,它左侧最大值是 3边界,右侧最大值是 9,上方 3,下方 3,四者最小值是 3,水位 3,存水 2。看起来也对。问题的真正暴露是在我构造了一个迷宫式地形之后3 3 3 3 3 3 1 1 1 3 3 1 3 1 3 3 1 1 1 3 3 3 3 3 3四方向最值法给出的答案和真实答案一致,因为地形太规则了。我一度以为这个思路可行,直到我想明白它的本质缺陷四方向前缀最大值只能处理凸出的地形,处理不了凹进去的走廊。如果水要绕过一个障碍物才能流出去,四个轴向的前缀最大值完全捕捉不到这种绕行路径。我构造了一个 S 形走廊的用例之后,这个方法彻底破产。这个弯路的教训是一维结论的成立依赖路径只有两条这个强假设,凡是把这个假设去掉的推广,都必须回到最小瓶颈路径这个原始定义。4.2 第二次尝试从边界向内 BFS,取最小的那个上界第二个思路我觉得已经很接近了。既然边界水位已知,那我从所有边界格子同时开始 BFS,每一层水位取当前水位和邻居高度的较大值,这样传播下去就得到答案。麻烦的是,用普通队列的 BFS,层与层之间不保证按水位有序,一个高水位的传播可能先于低水位的传播到达某个格子,导致这个格子被赋予了一个偏大的水位上界,而且这个错误值会被继续传播下去。我当时是用一个小数据 骗 过自己的3 3 3 3 1 3 3 3 3普通队列的处理顺序恰好是从边界往里推,水位 3 传进去,答案 2,正确。但把规模放大到 5x5、地形稍微复杂一点,结果就开始飘忽。我一度以为是visited的问题,在那边反复折腾了半小时,后来才意识到根源在于处理顺序——我需要的不是先进先出,而是每次都取当前水位最小的那个点。这不就是优先队列吗。从 BFS 到最小堆的这一步,其实是把算法从图的遍历升级成了贪心扩展,性质完全不同。普通 BFS 只有在所有边权相等时才等价于最短路,而这里每个点的代价是它的高度,各不相同。4.3 第三次尝试换最小堆之后,又栽在两个细节上改成优先队列之后逻辑一下就通了,但代码层面还有两个坑等着。第一个是visited标记的时机。我一开始写的是在出堆的时候才标记访问——理由是只有出堆了才说明它的水位确定了。这个逻辑听起来对,实际上会带来严重的性能问题同一个格子可能被多个邻居重复入堆,堆的体积从O(mn)膨胀到O(4mn),虽然常数只有 4 倍,但入堆出堆的次数翻了好几倍,在大数据上直接超时。更隐蔽的是,如果某个格子被重复入堆,第二次弹出时它的邻居已经访问过了,不会重复计水,所以答案仍然正确——这让这个 bug 更难被发现,你只会看到超时,不知道问题在哪。正确的做法是在入堆的同时就标记visited,因为一个格子一旦被任何一个水位已经确定的点扩展到了,它的水位就已经定下来了,后面再来更差的上界毫无意义。第二个坑是邻居水位的计算。我最初写成了pq.offer(new int[]{h, nx, ny}),直接把当前水位继承给邻居,忘了取 max。这个 bug 我在小数据上完全没测出来,直到第 4.4 节要讲的那个用例。4.4 一次对拍,把漏掉 max 的 bug 揪了出来漏掉 max 之后,我构造了这样一个 5x5 地形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外面一圈高度 2,里面一圈是高度 9 的环,环中心是一个高度 1 的坑。正确答案很显然中心那个坑被 9 高的环团团围住,水位就是 9,存水量9 - 1 8。正确代码跑出来是 8,这没问题。而漏掉max的那版跑出来是 1。原因很好理解外层水位 2 的边界点扩展时,碰到高度 9 的环,它把水位 2 直接塞给了这些 9 高的格子。这些格子入堆时水位被削成了 2,等它们再去扩展中心那个坑的时候,带着 2 的水位过去,只贡献了2 - 1 1。整整少了 7 单位水。这个样例我后来一直留着当回归测试。它的价值在于只有当地形里存在外圈水位低、内圈水位高的嵌套结构时,漏掉 max 的错误才会显现。官方样例和大部分随手构造的用例都是单层结构,水位单调地从外向内递减,根本暴露不出来。4.5 几类高频细节错误的对症清单除了上面两个,还有几个小问题也值得记一下。我把它们整理成一张表,方便对照排查。现象可能原因定位方法小数据正确,大数据答案偏小邻居水位没取 max用 4.4 的嵌套环样例验证结果正确但超时visited 在出堆时才标记,堆被重复元素撑爆打印堆的最大尺寸,正常应约等于 mn答案忽大忽小,不稳定用了普通队列或大顶堆换成PriorityQueue或heapq再跑数组越界二维坐标线性化时用了i * m j统一改成i * n j,或者干脆不线性化边界行/列处理遗漏只判断了i 0忘了i m - 1写成一个isBorder函数复用关于i * n j这一点多说一句。我不止一次在面试现场看到有人写成i * m j,因为m出现在行数位置上显得很顺手。这个错误在方阵上完全不会暴露,一旦遇到非方阵就立刻崩,而且报的是越界异常,和真正的原因隔了好几层。如果不想纠结,直接用二维数组或者(i, j)元组最省心。还有个小优化当m 3或n 3时直接返回 0。这个判断不是必须的——即使不加,通用逻辑跑下来答案也是 0,因为所有格子一开始就是边界点,全部被标记访问,后面不会有任何扩展。但加上的话能省掉一整轮堆操作,在一行或者两列的极端输入上还是有意义的。5. 换一个视角用并查集求最小瓶颈路径,顺便理解题目本质如果你把第 1 章的公式记住了,会发现 407 本质上就是每个点到外部的最小瓶颈值这个经典问题。而最小瓶颈路径有一个非常漂亮的离线解法,用并查集加排序就能做,完全不需要优先队列。5.1 引入一个虚拟外部节点,把边界条件变成一条边这个解法最妙的地方是引入一个虚拟节点,叫它OUT,代表矩阵外面那个无限大的空间。然后我们把网格重新看成一张图每个格子是一个节点,相邻格子之间连一条边,边的权重是这两个格子高度的较大值——这条边的含义是水要通过这两个格子,至少得翻过这么高的墙。关键的转换在边界上每个边界格子都和虚拟节点OUT连一条边,权重就是这个边界格子自身的高度。这样一来,水从某个格子流到矩阵外面就变成了从该格子沿着某条路径走到OUT这个纯粹的图论问题,水位就是这条路径上最大边权的最小可能值,也就是最小瓶颈路径。5.2 用 Kruskal 的顺序合并,第一次连上外部时结算水位接下来按边权从小到大排序,依次处理每条边,用并查集维护连通块。当一条边连接的两个端点不在同一个连通块时,就把它们合并。合并的时候做一件事如果一边的连通块已经接触过OUT,而另一边还没接触过,那么没接触的那一边里所有格子的水位就确定为当前这条边的权重。这个结论为什么成立可以用反证法想清楚。设当前边的权重是w,那个还没接触OUT的连通块叫S。S里任意一个格子x,它到OUT的最小瓶颈不可能小于w,因为如果小于w,说明存在一条最大边权小于w的路径让x连到了外面,那么在处理到那条路径上权重最大的边时那个权重小于w,x就应该已经和OUT连通了,矛盾。而它也不可能大于w,因为走S内部到当前这条边再到OUT这条路,瓶颈最大就是w。两头一夹,S里所有格子的水位都恰好等于w。这个论证干净得让人舒服,它同时也解释了为什么同权边可以任意顺序处理——只要同一层权重的边全部处理完再结算,结果都一样。5.3 并查集版本的代码,以及两个容易写崩的地方class Solution: def trapRainWater(self, heightMap) - int: m, n len(heightMap), len(heightMap[0]) if m 3 or n 3: return 0 N m * n OUT N # 虚拟外部节点编号 parent list(range(N 1)) members [[i] for i in range(N 1)] # 每个集合的成员列表 has_out [False] * (N 1) has_out[OUT] True water [0] * N # 每个格子的水位 def find(x): while parent[x] ! x: parent[x] parent[parent[x]] x parent[x] return x edges [] for i in range(m): for j in range(n): u i * n j if i 0 or i m - 1 or j 0 or j n - 1: edges.append((heightMap[i][j], u, OUT)) if i 1 m: v (i 1) * n j edges.append((max(heightMap[i][j], heightMap[i 1][j]), u, v)) if j 1 n: v i * n j 1 edges.append((max(heightMap[i][j], heightMap[i][j 1]), u, v)) edges.sort() for w, a, b in edges: ra, rb find(a), find(b) if ra rb: continue # 按集合大小合并,保证 members 的合并是 O(N log N) if len(members[ra]) len(members[rb]): ra, rb rb, ra # 只有一边接触外部时,另一边所有格子的水位才被确定 if has_out[ra] ! has_out[rb]: inner rb if has_out[ra] else ra for x in members[inner]: water[x] w parent[rb] ra has_out[ra] has_out[ra] or has_out[rb] members[ra].extend(members[rb]) members[rb] [] ans 0 for i in range(m): for j in range(n): v i * n j if water[v] heightMap[i][j]: ans water[v] - heightMap[i][j] return ans两个容易写崩的地方。第一个是members数组的内存,如果直接给每个节点初始化一个列表,200 * 200 1个空列表的开销不小,在 Python 里大约要占十几兆。可以先只存单元素列表,合并时用extend把小的并到大的里,这样总体的合并代价是O(N log N),不会退化。第二个是结算时机。water[x] w这个赋值必须在合并之前做,而且只对没接触外部的那一侧做。如果你图省事,在合并之后统一判断has_out,那时has_out[ra]已经变成True了,你会把整个合并后的大集合都赋值一遍,包括那些早就应该在更小水位处结算过的格子,结果就是水位被反复覆盖,答案全乱。从工程角度讲,这道题我依然推荐优先队列版本,代码短、不容易写错、面试时能讲清楚不变量。并查集版本更适合用来加深理解,或者在某些需要离线处理所有点的场景里作为工具积累——如果你在刷 leetcode 热门100题或者准备 leetcode 周赛430 这类需要快速手写并查集的场合,这套最小瓶颈路径的模板值得默写两遍。6. 复杂度、对拍验证,以及这道题到底该练什么最后聊聊工程层面的东西。很多人做完一道题就切下一道,其实这道题有几个额外收益,值得多花二十分钟把边角都摸一遍。6.1 O(mn log(mn)) 是怎么来的,以及常数都花在哪优先队列版本的时间复杂度是O(mn log(mn))。每个格子最多入堆一次——这一点由入堆即标记访问保证——所以入堆出堆的总次数是O(mn),每次堆操作是O(log(mn)),乘起来就是总复杂度。空间上是O(mn),主要消耗在visited数组和堆上。并查集版本同样是O(mn log(mn)),不过常数项花在不同的地方。边数是O(mn)级别每个格子最多连出两条不重复的边,加上边界格子连向OUT的边,排序是O(mn log(mn))并查集本身因为带了路径压缩和按大小合并是接近线性的,但members的合并需要O(N log N)的额外开销。实际跑下来,并查集版本通常会比优先队列版本慢一些,因为 Python 的排序和对象操作都不便宜。需要注意的是,这道题的高度上限是两万,答案最大会到200 * 200 * 20000 8 * 10^8,完全在 32 位整数范围内,不需要开long。但如果题目改一改,把高度上限提到10^9,那就得换成 64 位了。养成看一眼数据范围再决定类型的习惯,能省掉不少莫名奇妙的 WA。6.2 用暴力做对拍,十分钟验证自己的实现我最推荐的验证方式是自己写一个暴力版本对拍。思路很直白对每个格子单独跑一次最小瓶颈路径的 Dijkstra,终点是任何边界格子,得到的距离就是它的水位。这份代码慢得离谱,O(mn * mn log(mn)),但只有三十行,不容易写错。import heapq def brute(heightMap): m, n len(heightMap), len(heightMap[0]) total 0 dirs ((1, 0), (-1, 0), (0, 1), (0, -1)) for si in range(m): for sj in range(n): dist [[float(inf)] * n for _ in range(m)] dist[si][sj] heightMap[si][sj] pq [(heightMap[si][sj], si, sj)] best heightMap[si][sj] while pq: d, x, y heapq.heappop(pq) if d dist[x][y]: continue # 一旦扩展到边界,当前距离就是该格子到外部的最小瓶颈 if x 0 or x m - 1 or y 0 or y n - 1: best d break for dx, dy in dirs: nx, ny x dx, y dy if 0 nx m and 0 ny n: nd max(d, heightMap[nx][ny]) if nd dist[nx][ny]: dist[nx][ny] nd heapq.heappush(pq, (nd, nx, ny)) total max(0, best - heightMap[si][sj]) return total有了它,就可以随机生成 4x4 到 6x6、高度在 0 到 9 之间的小矩阵,跑几千组对拍。我实感的经验是,高度范围越窄,越容易生成嵌套环多层盆地这类暴露 bug 的地形。如果高度范围开到 0 到 100,随机地形往往很平缓,反而不容易发现问题。6.3 这道题真正该练到手的是什么如果你只是为了通过这道题,最小堆加 BFS 的模板背下来就够了。但我觉得 407 的价值在于它逼着你把两件事想透。第一件是优先队列 BFS这个模式本身。它不是 407 独有的,0-1 BFS、多源最短路、拓扑排序里的最小字典序、甚至某些贪心构造题,内核都是同一套东西当你需要按某种单调的代价顺序处理节点,而处理每个节点又会产生新的候选节点时,优先队列就是那个天然的调度器。407 的特别之处在于,它的代价是max而不是,但单调性和切分性质依然成立,所以算法照样跑得通。想清楚为什么max也满足单调性,比记住代码本身重要得多。第二件是最小瓶颈路径和并查集的连接。很多人把并查集当成一个只用来做连通性判断的黑盒,其实它在离线最短路问题里有一整套用法,Kruskal重构树、带权并查集、最小瓶颈路径都属于这个家族。407 的并查集解法是这方面最友好的入门例子之一,因为它的图结构和边界条件都足够直观。至于那道经常被拿来一起刷的 leetcode 073 爱吃香蕉的狒狒,它考的是二分答案,和这道题没什么关系,别被都是困难题这个标签误导了。真正和 407 互为补充的是一维的 42 题、二维矩阵里的最短路系列,以及各种需要维护当前最小候选的贪心题。我在实际练习的时候,喜欢把 42 和 407 的代码放在同一个文件里对比着看,一维的写法是怎么退化成二维的特例的,看一眼就明白了。
