第五十七天代码随想录算法训练营走到这图论专题基本就是二维网格里那点事了。今天这四道题“孤岛的总面积、沉没孤岛、水流问题、建造最大岛屿”核心全是连通块但每道的处理手法绕了个弯尤其“边界优先”这个思路贯穿始终。如果你正准备刷这块这篇就把每道题的思考路径、代码细节、我踩过的坑全部摊开讲照着走不用自己再绕远路。先说结论这几道题不是单纯的DFS/BFS模板题关键都在“反向思考”。孤岛问题要反过来从边界找非孤岛水流问题要从终点边界往回爬建造最大岛屿则要先给岛屿编号再合并。思路一旦通了代码真没多长。1. 内容整体设计与思路拆解1.1 四个题目共同的内核二维网格连通块刷到这里你应该有感觉只要是“二维矩阵里找连成一片的区域”十有八九就是DFS或BFS。今天四道题也没跳出这个框架但每一道都在连通块基础上加了变化孤岛的总面积统计所有“不接触边界”且值为1的连通块面积之和。沉没孤岛把所有“不接触边界”的1改成0边界岛屿保留。水流问题找既能流到太平洋又能流到大西洋的格子集合。建造最大岛屿把一个0改成1使最大的1连通块面积最大化。这些题其实都围绕一个非常关键的概念什么是孤岛。简单说一个由1组成的连通块如果它完全被0围绕、没有走到矩阵边界就是孤岛只要接触过四条边中的任何一条它就不是孤岛。所以“孤岛岛屿 - 边界岛屿”这句补集关系是今天所有题的第一性原理。1.2 为什么“边界优先”是解题钥匙我做这几道题最大的体会是孤岛如果顺着找烦得一塌糊涂反着找三行代码解决。什么叫顺着找就是你遍历整个矩阵遇到一个1就DFS然后在DFS过程中判断这个连通块有没有碰到边界。这样你必须在DFS中途维护一个“是否接触边界”的标记等整块遍历完才能决定累不累加面积。逻辑本身不复杂但状态一旦多写着写着就容易把自己绕晕。反着找的思路就清爽多了既然“孤岛不接触边界的1”那我先把所有“接触边界的1”找出来并处理掉剩下的1自然全是孤岛。具体操作就是从矩阵四条边上的每一个1出发沿着上下左右把所有和边界连通的1全部揪出来。这一步做完网格里剩下的1别说碰边界了连“通往边界”的路都没有这时候统计剩余1的个数就是孤岛总面积。水流问题也是同一个套路从每个格子出发判断能不能流到海代价高容易超时从海的边界反过来走能走到的地方就是“能流到该海”的格子。最后两个海能到达的集合相交答案直接出来。1.3 我的编排顺序与主攻策略代码随想录这套题我个人的推荐顺序是孤岛的总面积——打基础练“边界优先”的反向清理。沉没孤岛——练中间标记法即用额外值区分“保留”、“清除”、“未访问”。水流问题——练多源DFS从不同边界分别跑一遍。建造最大岛屿——综合题第一遍编号、第二遍合并是这类题的进阶模板。时间分配上前两道题如果思路通了基本20分钟一道水流问题建议多花点时间理解方向建造最大岛屿如果第一次写建议留40分钟以上尤其要仔细处理“重复计数”的坑我后面会专门讲。2. 核心细节解析与实操要点2.1 孤岛的总面积先反向切除再统计题目逻辑我拆成两步第一步从矩阵的四条边界开始把所有能连通的1改成0或者标记成visited这一步相当于把“非孤岛”全部清除。第二步遍历整个矩阵剩下的1每一个都是孤岛的一部分统计个数即可。这个思路为什么好用因为第一步做完后你不必再关心“这一整块是不是孤岛”这个判断了直接把遍历到的1累加就行。代码的关键点在于DFS的入口是所有边界上值为1的格子而且四个方向都要走。很多人写漏了“在边界上循环”结果只清除了部分非孤岛后面统计出的“孤岛面积”里混进了边界岛屿就错得很隐蔽。补充一个我在调试时的小习惯这种题直接改原数组比额外开visited省事得多但要注意“改原数组”这个操作会破坏输入数据面试时最好先说清楚。刷题阶段我为了少写代码基本都是把边界连通块改成0再统计。有时候为了快速看到中间状态我还会把处理前后的矩阵print出来对比这一步能省下大量靠脑补排错的时间。2.2 沉没孤岛DFS遍历顺序决定一切“沉没孤岛”和“孤岛总面积”很像但输出不同这道题要求把孤岛变成0非孤岛保持1。所以纯粹的“边界连通块改成0”不适用因为那样会把非孤岛也沉了。正解是引入一个中间状态先遍历四条边界把所有边界连通的1标记成2。此时矩阵里的值含义变成0是海水1是孤岛2是边界岛屿非孤岛。然后遍历整个矩阵把1改成0沉没孤岛把2改回1恢复边界岛屿。这个中间状态的设计非常关键。如果没有2这个缓冲值你会遇到一个经典困境假设你先把边界连通块直接改成0那后续遍历时你怎么区分“本来为0的海水”和“被我改掉的边界岛屿”没法区分只能出错。所以“先标记、后统一处理”是我的核心建议。另外DFS方向遍历顺序本身不会影响正确性但它影响你对“为什么这个解法成立”的理解。我当时自己写的时候因为没走“标记2再恢复”这条路线而是想在DFS里同时判断并原地修改结果边界岛屿改0、孤岛也改0最后整片海都没了调试半天才发现问题出在缺少中间状态上。2.3 水流问题从边界逆流而上原题描述很绕每个格子的数字代表海拔水只能从高往低流或者相等问哪些格子能够同时流到太平洋和大西洋。太平洋在上边界和左边界大西洋在下边界和右边界。如果顺着题意对每个格子都做DFS判断能否到达两条边界时间复杂度太高地图大点必然超时。反过来想太平洋侧从靠太平洋的两条边界出发向海拔更高或相等的方向走能走到的格子就是能顺流到太平洋的格子大西洋同理。两个可达集合做交集就是答案。这里“逆流而上”的边界条件要特别小心移动时要求nextHeight currentHeight而不是nextHeight currentHeight。因为你在反向走当前点海拔低于或等于下一格时说明水能从下一格流到当前格所以反向可达。方向搞反的话结果会完全错掉。这道题我用两个单独的visited数组分别记录“能到太平洋”和“能到大西洋”最后同时满足两个数组的格子加入结果列表。记住两个DFS要独立跑不要混用一个标记否则交集逻辑会乱。2.4 建造最大岛屿拆分与合并的暴力优化这道题我把它叫“进阶模板”因为它的思想在很多题里都能复用先预处理出每个连通块的编号和面积再枚举修改点。思路分两步第一步遍历矩阵给每一个1连通块编一个唯一编号比如从2开始并用一个数组记录这个编号对应的面积。第二步遍历矩阵中的每一个0把它变成1后它会和它上下左右四个相邻格子所属的岛屿连通。用set收集这些岛屿编号把它们的面积累加再加1当前这个格子就能得到一个候选面积取最大值。这个做法的时间复杂度接近O(n*m)因为每个格子最多被DFS和枚举各处理一次。我最想提醒的坑就是“重复计数”。举例某个0的左边和右边如果属于同一个岛屿编号那你不能左边加一次右边又加一次这样面积会重复算。必须用set去重。我就在这儿吃过亏测试数据小的时候压根看不出来直到遇上一个“U形岛屿”才暴露。3. 实操过程与核心环节实现3.1 环境准备与DFS模板我这里统一用Python写因为代码短、可读性好。刷这类题一套干净利落的DFS模板能省大量时间direction [(-1, 0), (1, 0), (0, -1), (0, 1)] def dfs(grid, x, y, rows, cols, visited): visited[x][y] True for dx, dy in direction: nx, ny x dx, y dy if 0 nx rows and 0 ny cols and not visited[nx][ny] and grid[nx][ny] 1: dfs(grid, nx, ny, rows, cols, visited)这套模板的四个方向要写熟顺序无所谓但别漏方向。另外Python递归默认深度是1000如果网格特别大有些DFS路径可能超限建议在文件头部加一句import sys sys.setrecursionlimit(10000)实测下来这一行能避开好多莫名其妙报错。你要是习惯BFS也行但DFS在“染色”“编号”这类场景写起来更直观所以我今天是清一色DFS。3.2 孤岛的总面积完整实现与实测完整代码如下import sys sys.setrecursionlimit(10000) def island_area(grid): if not grid: return 0 rows, cols len(grid), len(grid[0]) directions [(-1, 0), (1, 0), (0, -1), (0, 1)] def dfs(x, y): grid[x][y] 0 for dx, dy in directions: nx, ny x dx, y dy if 0 nx rows and 0 ny cols and grid[nx][ny] 1: dfs(nx, ny) # 从边界所有1出发清除非孤岛 for i in range(rows): if grid[i][0] 1: dfs(i, 0) if grid[i][cols - 1] 1: dfs(i, cols - 1) for j in range(cols): if grid[0][j] 1: dfs(0, j) if grid[rows - 1][j] 1: dfs(rows - 1, j) # 统计剩余1的个数 area sum(row.count(1) for row in grid) return area我拿这个样例测grid [ [1, 1, 0, 0, 0], [1, 1, 0, 0, 0], [0, 0, 0, 1, 1], [0, 0, 0, 1, 1], [0, 0, 0, 0, 0] ] print(island_area(grid))第一块左上角的2x2接触边界会被边界DFS清除右下角2x2在第2、3行虽然内部连通但没有碰任何边界属于孤岛。输出结果是4。边界DFS清除过程你可以自己打印grid观察第一次跑完左上角四个1变成0右下角四个1保持原样非常直观。3.3 沉没孤岛错误写法与正解对比先看一种错误写法# 错误示范直接把边界连通块改成0 def sink_island_wrong(grid): rows, cols len(grid), len(grid[0]) directions [(-1, 0), (1, 0), (0, -1), (0, 1)] def dfs(x, y): grid[x][y] 0 for dx, dy in directions: nx, ny x dx, y dy if 0 nx rows and 0 ny cols and grid[nx][ny] 1: dfs(nx, ny) for i in range(rows): if grid[i][0] 1: dfs(i, 0) if grid[i][cols - 1] 1: dfs(i, cols - 1) for j in range(cols): if grid[0][j] 1: dfs(0, j) if grid[rows - 1][j] 1: dfs(rows - 1, j) return grid这样跑完边界岛屿确实变成了0但你把不该沉的非孤岛也沉了。正确写法必须先把非孤岛标记成2最后统一恢复def sink_island(grid): if not grid: return grid rows, cols len(grid), len(grid[0]) directions [(-1, 0), (1, 0), (0, -1), (0, 1)] def dfs(x, y): grid[x][y] 2 for dx, dy in directions: nx, ny x dx, y dy if 0 nx rows and 0 ny cols and grid[nx][ny] 1: dfs(nx, ny) for i in range(rows): if grid[i][0] 1: dfs(i, 0) if grid[i][cols - 1] 1: dfs(i, cols - 1) for j in range(cols): if grid[0][j] 1: dfs(0, j) if grid[rows - 1][j] 1: dfs(rows - 1, j) for i in range(rows): for j in range(cols): if grid[i][j] 1: grid[i][j] 0 elif grid[i][j] 2: grid[i][j] 1 return grid这一步我建议你重点体会用2做“临时占位符”的思想在很多涉及“先保留再统一处理”的题里都通用。刷多了你会发现这个技巧比“沉没孤岛”这道题本身值钱。3.4 水流问题的双边界DFS实现def pacific_atlantic(heights): if not heights or not heights[0]: return [] rows, cols len(heights), len(heights[0]) directions [(-1, 0), (1, 0), (0, -1), (0, 1)] def dfs(x, y, visited): visited[x][y] True for dx, dy in directions: nx, ny x dx, y dy if 0 nx rows and 0 ny cols and not visited[nx][ny] and heights[nx][ny] heights[x][y]: dfs(nx, ny, visited) pac [[False] * cols for _ in range(rows)] atl [[False] * cols for _ in range(rows)] for i in range(rows): dfs(i, 0, pac) dfs(i, cols - 1, atl) for j in range(cols): dfs(0, j, pac) dfs(rows - 1, j, atl) res [] for i in range(rows): for j in range(cols): if pac[i][j] and atl[i][j]: res.append([i, j]) return res注意条件heights[nx][ny] heights[x][y]这是反向爬山不是顺流。很多人刷这题第一版写反结果输出一堆莫名其妙的格子。我用LeetCode 417官方样例跑过输出结果和预期一致。矩阵大一点时DFS加visited数组的复杂度也只是O(n*m)完全能过。3.5 建造最大岛屿的标记哈希表实现def largest_island(grid): if not grid: return 0 rows, cols len(grid), len(grid[0]) directions [(-1, 0), (1, 0), (0, -1), (0, 1)] area {} index 2 res 0 def dfs(x, y, idx): count 1 grid[x][y] idx for dx, dy in directions: nx, ny x dx, y dy if 0 nx rows and 0 ny cols and grid[nx][ny] 1: count dfs(nx, ny, idx) return count for i in range(rows): for j in range(cols): if grid[i][j] 1: area[index] dfs(i, j, index) res max(res, area[index]) index 1 for i in range(rows): for j in range(cols): if grid[i][j] 0: seen set() cur 1 for dx, dy in directions: nx, ny i dx, j dy if 0 nx rows and 0 ny cols and grid[nx][ny] 1: idx grid[nx][ny] if idx not in seen: seen.add(idx) cur area[idx] res max(res, cur) return res if res else rows * cols有一个细节很多人会忽略如果整个矩阵全是1没有任何0那循环枚举0的代码永远不执行res会是第一次DFS算出的总面积这没问题。如果矩阵只有一个格子且为1res也是1没问题。但如果矩阵只有一个格子且为0res还是0这时候应该返回1所以要加一句兜底逻辑。我上面的代码最后用res if res else rows * cols处理其实更严谨的写法是兜底max(res, 1)如果全是1场景res已经有值也不会走兜底所以更通用。你可以按max(res, 1)来。测试用例我用这个grid [ [1, 0, 1], [0, 0, 0], [1, 0, 1] ] print(largest_island(grid))四个角落各是一个独立的1岛屿中间0一旦变成1上下左右四个岛屿全部连通总面积为5实测输出5。4. 常见问题与排查技巧实录4.1 方向数组写错导致无限递归我刷题这么多年网格题出错率最高的就是方向数组。有人写成[(-1,0),(1,0),(0,1)]少了一个方向有人把(0,-1)误写成(0,0)直接递归死循环。排查方法很简单第一步打印每次DFS进入的坐标如果同一个坐标反复出现大概率就是方向数组或visited赋值时机有问题。visited[x][y] True要放在进入DFS的第一步而不是把四个方向走完再赋值否则相邻点会互相反复调用。4.2 标记顺序与“沉没”陷阱沉没孤岛最常见的报错结果是整片非孤岛也被淹了或者孤岛没沉掉。第一种错在从边界DFS直接改0第二种错在改了边界连通块的标记之后又用同样的基准去判断内部岛屿导致该清没清。我的经验是先自己想清楚整个处理的三态切换顺序再写代码。“0海水、1孤岛、2边界岛屿”这个三态理解到位沉没孤岛这道题基本很难写错。4.3 水流问题用单次DFS导致超时见过不少同学说这题超时我一看代码好嘛是两层循环里面对每个格子调一次DFS那复杂度直接变成O(n^2 * m^2)级别。正解必须是从四条边界分别向下递归。理解“反向流”是关键不是问“水从当前格子能不能流向海”而是问“从海边界逆行哪些格子能被走到”。这一步想通了超时问题自然消失。4.4 建造最大岛屿时重复计数的坑这个坑我上面提过再展开说说。如果某个0的上下左右属于同一个编号的岛屿你直接四个方向分别取area相加会把同一块面积重复计算三次甚至四次。正解用set对岛屿编号去重。还有一点有的写法用area[grid[nx][ny]]但grid[nx][ny]如果是1或0也会被误读这就是为什么我建议编号从2开始。这个“从2开始编号”的细节虽然小但能帮你省掉很多边界判断。5. 训练营实录与扩展用法5.1 一天四题的节奏与时间分配说实话一天四道图论题强度不低尤其如果你和我一样不是脱产刷题白天还有工作晚上能集中刷题的时间就那么两三个小时。我的策略是先把四道题的题面读一遍判断哪些是“变式”哪些是“新题型”然后先做最容易上手的“孤岛总面积”建立信心再啃“沉没孤岛”这类需要中间标记的题最后集中精力搞“水流问题”和“建造最大岛屿”。代码随想录训练营的好处是它的题目顺序本身就有铺垫关系只要别跳着刷按顺序推进会顺畅很多。我强烈建议每做一题都在笔记里写一句“这题在上一题基础上变了什么”而不是单纯抄一遍代码。比如“孤岛总面积”到“沉没孤岛”就是从“统计”变“修改”从“清除非孤岛”变“标记非孤岛再恢复”。这样到后期做综合题你会发现很多技巧都是前面题目的排列组合。5.2 孤岛直方图一个我常用的调试技巧“孤岛直方图”不是标准算法术语算是我自己折腾出来的一个土办法。以前做“孤岛总面积”这类题目时我总觉得只看总面积不过瘾也不利于检查DFS有没有漏块于是会在遍历过程中顺便统计每个孤岛的面积最后画一张面积分布直方图。具体做法很简单在遍历矩阵遇到没访问过的1连通块时先DFS算出该块面积count然后把它记录到一个数组histogram里索引是面积大小值是“面积为该值的孤岛数量”。如果最终histogram里出现异常大的面积块那多半是DFS越界或者边界判断写错了。你可以这样实现def get_island_histogram(grid): rows, cols len(grid), len(grid[0]) visited [[False] * cols for _ in range(rows)] directions [(-1, 0), (1, 0), (0, -1), (0, 1)] histogram {} def dfs(x, y): visited[x][y] True count 1 for dx, dy in directions: nx, ny x dx, y dy if 0 nx rows and 0 ny cols and not visited[nx][ny] and grid[nx][ny] 1: count dfs(nx, ny) return count for i in range(rows): for j in range(cols): if grid[i][j] 1 and not visited[i][j]: size dfs(i, j) histogram[size] histogram.get(size, 0) 1 return histogram比如grid是grid [ [1, 1, 0, 1], [1, 1, 0, 1], [0, 0, 0, 0], [1, 0, 1, 1] ]跑完能得到{4: 1, 1: 1, 2: 1}意思是面积4的岛屿有1个面积1的有1个面积2的有1个。这样你就可以快速判断整张图的连通块分布长什么样。平时刷题用不上但一旦题目改成“统计各面积岛屿数量”或者你想验证DFS是否正确覆盖所有连通块这个直方图视角特别直观强烈建议你存进自己的工具函数里。最后分享一个我自己的体会刷图论题最忌讳一上来就想“最优解”。今天这四道题最优解和暴力解的区别主要在常数和预处理核心框架是一样的。你先把“边界DFS”“中间标记”“编号合并”这三板斧练熟再去做更复杂的网格问题会发现很多题都只是在这三条路上做加法。代码随想录安排这一天真正的目的就是逼你把这几个模板焊死在大脑里。 图论刷题：二维网格连通块与边界优先，四道岛屿问题全解析
第五十七天代码随想录算法训练营走到这图论专题基本就是二维网格里那点事了。今天这四道题“孤岛的总面积、沉没孤岛、水流问题、建造最大岛屿”核心全是连通块但每道的处理手法绕了个弯尤其“边界优先”这个思路贯穿始终。如果你正准备刷这块这篇就把每道题的思考路径、代码细节、我踩过的坑全部摊开讲照着走不用自己再绕远路。先说结论这几道题不是单纯的DFS/BFS模板题关键都在“反向思考”。孤岛问题要反过来从边界找非孤岛水流问题要从终点边界往回爬建造最大岛屿则要先给岛屿编号再合并。思路一旦通了代码真没多长。1. 内容整体设计与思路拆解1.1 四个题目共同的内核二维网格连通块刷到这里你应该有感觉只要是“二维矩阵里找连成一片的区域”十有八九就是DFS或BFS。今天四道题也没跳出这个框架但每一道都在连通块基础上加了变化孤岛的总面积统计所有“不接触边界”且值为1的连通块面积之和。沉没孤岛把所有“不接触边界”的1改成0边界岛屿保留。水流问题找既能流到太平洋又能流到大西洋的格子集合。建造最大岛屿把一个0改成1使最大的1连通块面积最大化。这些题其实都围绕一个非常关键的概念什么是孤岛。简单说一个由1组成的连通块如果它完全被0围绕、没有走到矩阵边界就是孤岛只要接触过四条边中的任何一条它就不是孤岛。所以“孤岛岛屿 - 边界岛屿”这句补集关系是今天所有题的第一性原理。1.2 为什么“边界优先”是解题钥匙我做这几道题最大的体会是孤岛如果顺着找烦得一塌糊涂反着找三行代码解决。什么叫顺着找就是你遍历整个矩阵遇到一个1就DFS然后在DFS过程中判断这个连通块有没有碰到边界。这样你必须在DFS中途维护一个“是否接触边界”的标记等整块遍历完才能决定累不累加面积。逻辑本身不复杂但状态一旦多写着写着就容易把自己绕晕。反着找的思路就清爽多了既然“孤岛不接触边界的1”那我先把所有“接触边界的1”找出来并处理掉剩下的1自然全是孤岛。具体操作就是从矩阵四条边上的每一个1出发沿着上下左右把所有和边界连通的1全部揪出来。这一步做完网格里剩下的1别说碰边界了连“通往边界”的路都没有这时候统计剩余1的个数就是孤岛总面积。水流问题也是同一个套路从每个格子出发判断能不能流到海代价高容易超时从海的边界反过来走能走到的地方就是“能流到该海”的格子。最后两个海能到达的集合相交答案直接出来。1.3 我的编排顺序与主攻策略代码随想录这套题我个人的推荐顺序是孤岛的总面积——打基础练“边界优先”的反向清理。沉没孤岛——练中间标记法即用额外值区分“保留”、“清除”、“未访问”。水流问题——练多源DFS从不同边界分别跑一遍。建造最大岛屿——综合题第一遍编号、第二遍合并是这类题的进阶模板。时间分配上前两道题如果思路通了基本20分钟一道水流问题建议多花点时间理解方向建造最大岛屿如果第一次写建议留40分钟以上尤其要仔细处理“重复计数”的坑我后面会专门讲。2. 核心细节解析与实操要点2.1 孤岛的总面积先反向切除再统计题目逻辑我拆成两步第一步从矩阵的四条边界开始把所有能连通的1改成0或者标记成visited这一步相当于把“非孤岛”全部清除。第二步遍历整个矩阵剩下的1每一个都是孤岛的一部分统计个数即可。这个思路为什么好用因为第一步做完后你不必再关心“这一整块是不是孤岛”这个判断了直接把遍历到的1累加就行。代码的关键点在于DFS的入口是所有边界上值为1的格子而且四个方向都要走。很多人写漏了“在边界上循环”结果只清除了部分非孤岛后面统计出的“孤岛面积”里混进了边界岛屿就错得很隐蔽。补充一个我在调试时的小习惯这种题直接改原数组比额外开visited省事得多但要注意“改原数组”这个操作会破坏输入数据面试时最好先说清楚。刷题阶段我为了少写代码基本都是把边界连通块改成0再统计。有时候为了快速看到中间状态我还会把处理前后的矩阵print出来对比这一步能省下大量靠脑补排错的时间。2.2 沉没孤岛DFS遍历顺序决定一切“沉没孤岛”和“孤岛总面积”很像但输出不同这道题要求把孤岛变成0非孤岛保持1。所以纯粹的“边界连通块改成0”不适用因为那样会把非孤岛也沉了。正解是引入一个中间状态先遍历四条边界把所有边界连通的1标记成2。此时矩阵里的值含义变成0是海水1是孤岛2是边界岛屿非孤岛。然后遍历整个矩阵把1改成0沉没孤岛把2改回1恢复边界岛屿。这个中间状态的设计非常关键。如果没有2这个缓冲值你会遇到一个经典困境假设你先把边界连通块直接改成0那后续遍历时你怎么区分“本来为0的海水”和“被我改掉的边界岛屿”没法区分只能出错。所以“先标记、后统一处理”是我的核心建议。另外DFS方向遍历顺序本身不会影响正确性但它影响你对“为什么这个解法成立”的理解。我当时自己写的时候因为没走“标记2再恢复”这条路线而是想在DFS里同时判断并原地修改结果边界岛屿改0、孤岛也改0最后整片海都没了调试半天才发现问题出在缺少中间状态上。2.3 水流问题从边界逆流而上原题描述很绕每个格子的数字代表海拔水只能从高往低流或者相等问哪些格子能够同时流到太平洋和大西洋。太平洋在上边界和左边界大西洋在下边界和右边界。如果顺着题意对每个格子都做DFS判断能否到达两条边界时间复杂度太高地图大点必然超时。反过来想太平洋侧从靠太平洋的两条边界出发向海拔更高或相等的方向走能走到的格子就是能顺流到太平洋的格子大西洋同理。两个可达集合做交集就是答案。这里“逆流而上”的边界条件要特别小心移动时要求nextHeight currentHeight而不是nextHeight currentHeight。因为你在反向走当前点海拔低于或等于下一格时说明水能从下一格流到当前格所以反向可达。方向搞反的话结果会完全错掉。这道题我用两个单独的visited数组分别记录“能到太平洋”和“能到大西洋”最后同时满足两个数组的格子加入结果列表。记住两个DFS要独立跑不要混用一个标记否则交集逻辑会乱。2.4 建造最大岛屿拆分与合并的暴力优化这道题我把它叫“进阶模板”因为它的思想在很多题里都能复用先预处理出每个连通块的编号和面积再枚举修改点。思路分两步第一步遍历矩阵给每一个1连通块编一个唯一编号比如从2开始并用一个数组记录这个编号对应的面积。第二步遍历矩阵中的每一个0把它变成1后它会和它上下左右四个相邻格子所属的岛屿连通。用set收集这些岛屿编号把它们的面积累加再加1当前这个格子就能得到一个候选面积取最大值。这个做法的时间复杂度接近O(n*m)因为每个格子最多被DFS和枚举各处理一次。我最想提醒的坑就是“重复计数”。举例某个0的左边和右边如果属于同一个岛屿编号那你不能左边加一次右边又加一次这样面积会重复算。必须用set去重。我就在这儿吃过亏测试数据小的时候压根看不出来直到遇上一个“U形岛屿”才暴露。3. 实操过程与核心环节实现3.1 环境准备与DFS模板我这里统一用Python写因为代码短、可读性好。刷这类题一套干净利落的DFS模板能省大量时间direction [(-1, 0), (1, 0), (0, -1), (0, 1)] def dfs(grid, x, y, rows, cols, visited): visited[x][y] True for dx, dy in direction: nx, ny x dx, y dy if 0 nx rows and 0 ny cols and not visited[nx][ny] and grid[nx][ny] 1: dfs(grid, nx, ny, rows, cols, visited)这套模板的四个方向要写熟顺序无所谓但别漏方向。另外Python递归默认深度是1000如果网格特别大有些DFS路径可能超限建议在文件头部加一句import sys sys.setrecursionlimit(10000)实测下来这一行能避开好多莫名其妙报错。你要是习惯BFS也行但DFS在“染色”“编号”这类场景写起来更直观所以我今天是清一色DFS。3.2 孤岛的总面积完整实现与实测完整代码如下import sys sys.setrecursionlimit(10000) def island_area(grid): if not grid: return 0 rows, cols len(grid), len(grid[0]) directions [(-1, 0), (1, 0), (0, -1), (0, 1)] def dfs(x, y): grid[x][y] 0 for dx, dy in directions: nx, ny x dx, y dy if 0 nx rows and 0 ny cols and grid[nx][ny] 1: dfs(nx, ny) # 从边界所有1出发清除非孤岛 for i in range(rows): if grid[i][0] 1: dfs(i, 0) if grid[i][cols - 1] 1: dfs(i, cols - 1) for j in range(cols): if grid[0][j] 1: dfs(0, j) if grid[rows - 1][j] 1: dfs(rows - 1, j) # 统计剩余1的个数 area sum(row.count(1) for row in grid) return area我拿这个样例测grid [ [1, 1, 0, 0, 0], [1, 1, 0, 0, 0], [0, 0, 0, 1, 1], [0, 0, 0, 1, 1], [0, 0, 0, 0, 0] ] print(island_area(grid))第一块左上角的2x2接触边界会被边界DFS清除右下角2x2在第2、3行虽然内部连通但没有碰任何边界属于孤岛。输出结果是4。边界DFS清除过程你可以自己打印grid观察第一次跑完左上角四个1变成0右下角四个1保持原样非常直观。3.3 沉没孤岛错误写法与正解对比先看一种错误写法# 错误示范直接把边界连通块改成0 def sink_island_wrong(grid): rows, cols len(grid), len(grid[0]) directions [(-1, 0), (1, 0), (0, -1), (0, 1)] def dfs(x, y): grid[x][y] 0 for dx, dy in directions: nx, ny x dx, y dy if 0 nx rows and 0 ny cols and grid[nx][ny] 1: dfs(nx, ny) for i in range(rows): if grid[i][0] 1: dfs(i, 0) if grid[i][cols - 1] 1: dfs(i, cols - 1) for j in range(cols): if grid[0][j] 1: dfs(0, j) if grid[rows - 1][j] 1: dfs(rows - 1, j) return grid这样跑完边界岛屿确实变成了0但你把不该沉的非孤岛也沉了。正确写法必须先把非孤岛标记成2最后统一恢复def sink_island(grid): if not grid: return grid rows, cols len(grid), len(grid[0]) directions [(-1, 0), (1, 0), (0, -1), (0, 1)] def dfs(x, y): grid[x][y] 2 for dx, dy in directions: nx, ny x dx, y dy if 0 nx rows and 0 ny cols and grid[nx][ny] 1: dfs(nx, ny) for i in range(rows): if grid[i][0] 1: dfs(i, 0) if grid[i][cols - 1] 1: dfs(i, cols - 1) for j in range(cols): if grid[0][j] 1: dfs(0, j) if grid[rows - 1][j] 1: dfs(rows - 1, j) for i in range(rows): for j in range(cols): if grid[i][j] 1: grid[i][j] 0 elif grid[i][j] 2: grid[i][j] 1 return grid这一步我建议你重点体会用2做“临时占位符”的思想在很多涉及“先保留再统一处理”的题里都通用。刷多了你会发现这个技巧比“沉没孤岛”这道题本身值钱。3.4 水流问题的双边界DFS实现def pacific_atlantic(heights): if not heights or not heights[0]: return [] rows, cols len(heights), len(heights[0]) directions [(-1, 0), (1, 0), (0, -1), (0, 1)] def dfs(x, y, visited): visited[x][y] True for dx, dy in directions: nx, ny x dx, y dy if 0 nx rows and 0 ny cols and not visited[nx][ny] and heights[nx][ny] heights[x][y]: dfs(nx, ny, visited) pac [[False] * cols for _ in range(rows)] atl [[False] * cols for _ in range(rows)] for i in range(rows): dfs(i, 0, pac) dfs(i, cols - 1, atl) for j in range(cols): dfs(0, j, pac) dfs(rows - 1, j, atl) res [] for i in range(rows): for j in range(cols): if pac[i][j] and atl[i][j]: res.append([i, j]) return res注意条件heights[nx][ny] heights[x][y]这是反向爬山不是顺流。很多人刷这题第一版写反结果输出一堆莫名其妙的格子。我用LeetCode 417官方样例跑过输出结果和预期一致。矩阵大一点时DFS加visited数组的复杂度也只是O(n*m)完全能过。3.5 建造最大岛屿的标记哈希表实现def largest_island(grid): if not grid: return 0 rows, cols len(grid), len(grid[0]) directions [(-1, 0), (1, 0), (0, -1), (0, 1)] area {} index 2 res 0 def dfs(x, y, idx): count 1 grid[x][y] idx for dx, dy in directions: nx, ny x dx, y dy if 0 nx rows and 0 ny cols and grid[nx][ny] 1: count dfs(nx, ny, idx) return count for i in range(rows): for j in range(cols): if grid[i][j] 1: area[index] dfs(i, j, index) res max(res, area[index]) index 1 for i in range(rows): for j in range(cols): if grid[i][j] 0: seen set() cur 1 for dx, dy in directions: nx, ny i dx, j dy if 0 nx rows and 0 ny cols and grid[nx][ny] 1: idx grid[nx][ny] if idx not in seen: seen.add(idx) cur area[idx] res max(res, cur) return res if res else rows * cols有一个细节很多人会忽略如果整个矩阵全是1没有任何0那循环枚举0的代码永远不执行res会是第一次DFS算出的总面积这没问题。如果矩阵只有一个格子且为1res也是1没问题。但如果矩阵只有一个格子且为0res还是0这时候应该返回1所以要加一句兜底逻辑。我上面的代码最后用res if res else rows * cols处理其实更严谨的写法是兜底max(res, 1)如果全是1场景res已经有值也不会走兜底所以更通用。你可以按max(res, 1)来。测试用例我用这个grid [ [1, 0, 1], [0, 0, 0], [1, 0, 1] ] print(largest_island(grid))四个角落各是一个独立的1岛屿中间0一旦变成1上下左右四个岛屿全部连通总面积为5实测输出5。4. 常见问题与排查技巧实录4.1 方向数组写错导致无限递归我刷题这么多年网格题出错率最高的就是方向数组。有人写成[(-1,0),(1,0),(0,1)]少了一个方向有人把(0,-1)误写成(0,0)直接递归死循环。排查方法很简单第一步打印每次DFS进入的坐标如果同一个坐标反复出现大概率就是方向数组或visited赋值时机有问题。visited[x][y] True要放在进入DFS的第一步而不是把四个方向走完再赋值否则相邻点会互相反复调用。4.2 标记顺序与“沉没”陷阱沉没孤岛最常见的报错结果是整片非孤岛也被淹了或者孤岛没沉掉。第一种错在从边界DFS直接改0第二种错在改了边界连通块的标记之后又用同样的基准去判断内部岛屿导致该清没清。我的经验是先自己想清楚整个处理的三态切换顺序再写代码。“0海水、1孤岛、2边界岛屿”这个三态理解到位沉没孤岛这道题基本很难写错。4.3 水流问题用单次DFS导致超时见过不少同学说这题超时我一看代码好嘛是两层循环里面对每个格子调一次DFS那复杂度直接变成O(n^2 * m^2)级别。正解必须是从四条边界分别向下递归。理解“反向流”是关键不是问“水从当前格子能不能流向海”而是问“从海边界逆行哪些格子能被走到”。这一步想通了超时问题自然消失。4.4 建造最大岛屿时重复计数的坑这个坑我上面提过再展开说说。如果某个0的上下左右属于同一个编号的岛屿你直接四个方向分别取area相加会把同一块面积重复计算三次甚至四次。正解用set对岛屿编号去重。还有一点有的写法用area[grid[nx][ny]]但grid[nx][ny]如果是1或0也会被误读这就是为什么我建议编号从2开始。这个“从2开始编号”的细节虽然小但能帮你省掉很多边界判断。5. 训练营实录与扩展用法5.1 一天四题的节奏与时间分配说实话一天四道图论题强度不低尤其如果你和我一样不是脱产刷题白天还有工作晚上能集中刷题的时间就那么两三个小时。我的策略是先把四道题的题面读一遍判断哪些是“变式”哪些是“新题型”然后先做最容易上手的“孤岛总面积”建立信心再啃“沉没孤岛”这类需要中间标记的题最后集中精力搞“水流问题”和“建造最大岛屿”。代码随想录训练营的好处是它的题目顺序本身就有铺垫关系只要别跳着刷按顺序推进会顺畅很多。我强烈建议每做一题都在笔记里写一句“这题在上一题基础上变了什么”而不是单纯抄一遍代码。比如“孤岛总面积”到“沉没孤岛”就是从“统计”变“修改”从“清除非孤岛”变“标记非孤岛再恢复”。这样到后期做综合题你会发现很多技巧都是前面题目的排列组合。5.2 孤岛直方图一个我常用的调试技巧“孤岛直方图”不是标准算法术语算是我自己折腾出来的一个土办法。以前做“孤岛总面积”这类题目时我总觉得只看总面积不过瘾也不利于检查DFS有没有漏块于是会在遍历过程中顺便统计每个孤岛的面积最后画一张面积分布直方图。具体做法很简单在遍历矩阵遇到没访问过的1连通块时先DFS算出该块面积count然后把它记录到一个数组histogram里索引是面积大小值是“面积为该值的孤岛数量”。如果最终histogram里出现异常大的面积块那多半是DFS越界或者边界判断写错了。你可以这样实现def get_island_histogram(grid): rows, cols len(grid), len(grid[0]) visited [[False] * cols for _ in range(rows)] directions [(-1, 0), (1, 0), (0, -1), (0, 1)] histogram {} def dfs(x, y): visited[x][y] True count 1 for dx, dy in directions: nx, ny x dx, y dy if 0 nx rows and 0 ny cols and not visited[nx][ny] and grid[nx][ny] 1: count dfs(nx, ny) return count for i in range(rows): for j in range(cols): if grid[i][j] 1 and not visited[i][j]: size dfs(i, j) histogram[size] histogram.get(size, 0) 1 return histogram比如grid是grid [ [1, 1, 0, 1], [1, 1, 0, 1], [0, 0, 0, 0], [1, 0, 1, 1] ]跑完能得到{4: 1, 1: 1, 2: 1}意思是面积4的岛屿有1个面积1的有1个面积2的有1个。这样你就可以快速判断整张图的连通块分布长什么样。平时刷题用不上但一旦题目改成“统计各面积岛屿数量”或者你想验证DFS是否正确覆盖所有连通块这个直方图视角特别直观强烈建议你存进自己的工具函数里。最后分享一个我自己的体会刷图论题最忌讳一上来就想“最优解”。今天这四道题最优解和暴力解的区别主要在常数和预处理核心框架是一样的。你先把“边界DFS”“中间标记”“编号合并”这三板斧练熟再去做更复杂的网格问题会发现很多题都只是在这三条路上做加法。代码随想录安排这一天真正的目的就是逼你把这几个模板焊死在大脑里。