说起 LeetCode 上那些“刷题必遇”的经典题200. 岛屿数量绝对排得上前五。不管你是准备实习、秋招、春招还是单纯想把手里的 DFS、BFS 底子打牢这道题都绕不开。它在 LeetCode 热门 100 题里稳稳占了一个位置也是各大厂面试里出现频率极高的网格搜索题。这道题最妙的地方在于它不考什么高级技巧也不需要复杂的数学推导只要你理解“连通分量”这个概念会写最基础的深度优先或广度优先搜索就能给出一个面试官认可的标准答案。但反过来它考察的细节非常多——字符和数字的区分、边界检查的顺序、递归深度带来的栈溢出风险、要不要修改原始数据……每个点都能展开聊一聊。这篇文章我就以自己做这道题的实际经验为主线把 DFS、BFS、并查集三种思路都拆开揉碎了讲一遍再把平时容易被忽略的坑全部列出来。1. 题目本质与破题思路1.1 题面到底在说什么题目给你一个二维网格里面只有两种字符1代表陆地0代表水。岛屿的定义是“被水包围的、连续相邻的陆地区域”。这里的“相邻”有明确限定只能是上下左右四个方向斜对角不算。也就是说上面是 1、下面是 1、左边是 1、右边是 1 这样连成一片的才叫同一块岛屿。如果只是斜着碰到算两块独立的岛。举个最经典的例子网格是11110 11010 11000 00000左上角那五块 1 全部连在一起构成一个岛屿。虽然中间有个 0但 0 只是把右上角的 1 隔开了。右下角的 1 没有与任何其他 1 四方向相邻所以它是独立的一个岛屿。于是答案就是 2。另一个例子更直观11000 11000 00100 00011三块互不相连的陆地答案 3。核心就一句话数一数整个网格里有几个连通的陆地集团。1.2 破题核心把问题转化为连通分量计数如果你以前接触过图论其实一眼就能看出来——这个二维网格本质上就是一张图每个格子是一个节点上下左右相邻的格子之间有一条边。而岛屿的数量就是这张图中“值为 1 的节点”构成的连通分量的个数。连通分量的定义很简单在一个无向图里如果若干个节点彼此之间能通过边到达它们就在同一个连通分量里互相到不了的就是不同的分量。放到这个题目里同一座岛就是同一个连通分量。所以解题思路就变得很清晰遍历整个网格每次遇到一个没访问过的1就说明发现了一个新岛屿计数器加 1然后从它出发把所有跟它相连的1全部标记为“已访问”。这样下次遍历到它们时就不会再重复计数。这个“标记已访问”的动作可以用深度优先搜索DFS做可以用广度优先搜索BFS做也可以用并查集把所有相邻的 1 合并起来最后数一数有几个集合。三种方案殊途同归但各有各的适用场景。1.3 为什么它是 LeetCode 热搜榜单的常客说点刷题圈子里大家心照不宣的事LeetCode 热门 100 题里的题目几乎每道都对应着一类核心算法范式。像 073 爱吃香蕉的狒狒是二分答案的经典基本计算器是栈和表达式解析的经典而 200 岛屿数量就是图论搜索的入门必刷题。这道题能火这么多年我真的一点都不意外。它表面上是一道题实际上承担了三个功能第一它是你理解网格类 DFS/BFS 的敲门砖以后的扫雷游戏、迷宫寻路、腐烂的橘子全都从这个模板延伸出去第二它在面试里特别好使一个候选人会不会写边界检查、能不能分析递归栈、有没有意识到数据污染问题两三分钟就能看出来第三它跟真实世界的很多问题直接挂钩——图像处理里的连通域标记、地图上的湖泊岛屿统计、社交网络里的群组划分核心都是同一套逻辑。所以别觉得这题简单就不认真对待把它的每一个细节吃透后面的网格题你会走得很顺。2. DFS直觉解法的两种实现2.1 递归写法三句话搞定主逻辑DFS 是大多数人看到这道题的第一反应因为思路最贴合直觉发现一个岛就往四面八方扎进去把能走到的陆地全走一遍走不动了再回来。先看完整的 Java 递归解法class Solution { public int numIslands(char[][] grid) { if (grid null || grid.length 0) { return 0; } int rows grid.length; int cols grid[0].length; int count 0; for (int i 0; i rows; i) { for (int j 0; j cols; j) { if (grid[i][j] 1) { count; dfs(grid, i, j); } } } return count; } private void dfs(char[][] grid, int i, int j) { int rows grid.length; int cols grid[0].length; if (i 0 || i rows || j 0 || j cols || grid[i][j] 0) { return; } grid[i][j] 0; dfs(grid, i - 1, j); dfs(grid, i 1, j); dfs(grid, i, j - 1); dfs(grid, i, j 1); } }主函数里套一个双层循环碰到1就计数加 1然后调用dfs把这座岛“淹没”。这里的淹没就是把1改成0相当于标记已访问。dfs里的逻辑也简单先判断越界和当前格子是不是水如果是就返回如果当前格子是陆地立刻把它改成0再往上下左右四个方向递归。这里有几个细节我必须强调一下。第一边界检查的顺序很有讲究i 0 || i rows || j 0 || j cols这个判断必须放在最前面避免数组越界访问。第二判断必须是grid[i][j] 0而不是grid[i][j] ! 1虽然在这个题里结果一样但如果你把输入数据当成整数数组来做就会踩坑这个我后面专门讲。第三把当前格子改成0一定要在递归之前这叫“先标记后扩散”防止在递归过程中重复访问同一个格子否则会产生死循环。如果换用 Python代码更短核心思路完全一致class Solution: def numIslands(self, grid: List[List[str]]) - int: if not grid: return 0 m, n len(grid), len(grid[0]) def dfs(i, j): if i 0 or i m or j 0 or j n or grid[i][j] 0: return grid[i][j] 0 dfs(i - 1, j) dfs(i 1, j) dfs(i, j - 1) dfs(i, j 1) ans 0 for i in range(m): for j in range(n): if grid[i][j] 1: ans 1 dfs(i, j) return ans2.2 递归深度风险什么情况下必须换显式栈递归版本够简单但我要泼一盆冷水当你真正在刷题平台上提交或者在实际项目里遇到超大网格时递归深度可能成为最大的隐患。这道题目的输入约束通常是 300 × 300 以内理论上递归深度最多 90000 层。但 Java 默认的虚拟机栈深度通常只有几千到一万多层Python 的默认递归深度更是只有 1000 层。一旦网格全部是1DFS 一路扎进去可能直接触发StackOverflowError或RecursionError。我第一次在本地用 Python 跑一个 200 × 200 的全 1 网格时就遇到了递归深度超限。当时我还以为是代码写错了排查了半天才发现是递归层数的问题。所以在面试场景里如果你主动跟面试官讨论这个问题说“递归版本思路清晰但存在栈溢出风险我可以改成显式栈”这绝对是个加分项。显式栈版本是这样写的class Solution { public int numIslands(char[][] grid) { if (grid null || grid.length 0) { return 0; } int rows grid.length; int cols grid[0].length; int count 0; int[][] dirs {{1, 0}, {-1, 0}, {0, 1}, {0, -1}}; for (int i 0; i rows; i) { for (int j 0; j cols; j) { if (grid[i][j] 1) { count; Dequeint[] stack new ArrayDeque(); stack.push(new int[]{i, j}); grid[i][j] 0; while (!stack.isEmpty()) { int[] cur stack.pop(); for (int[] d : dirs) { int ni cur[0] d[0]; int nj cur[1] d[1]; if (ni 0 ni rows nj 0 nj cols grid[ni][nj] 1) { grid[ni][nj] 0; stack.push(new int[]{ni, nj}); } } } } } } return count; } }注意几个细节用ArrayDeque当栈比Stack类性能好每次把新节点压栈前就立刻标记为0而不是弹出时才标记这是避免重复入栈的关键方向数组dirs让四个方向的扩展代码变得非常简洁。实测下来显式栈在超大网格上的稳定性比递归好得多代码量增加的也有限。如果你在 LeetCode 上做题我建议至少动手写一遍这个版本因为它能帮你真正理解 DFS 的本质——显式栈模拟了系统递归栈的行为。3. BFS 与变形题实战3.1 标准 BFS一层一层地“感染”DFS 是“一条路走到黑”BFS 则是“一圈一圈往外扩”。思路同样直接发现一个陆地1把它作为起点放进队列然后一层一层地把周围的 1 全部感染成 0直到队列为空说明这一整座岛都被处理完了。class Solution { public int numIslands(char[][] grid) { if (grid null || grid.length 0) { return 0; } int rows grid.length; int cols grid[0].length; int count 0; int[][] dirs {{1, 0}, {-1, 0}, {0, 1}, {0, -1}}; for (int i 0; i rows; i) { for (int j 0; j cols; j) { if (grid[i][j] 1) { count; Queueint[] queue new ArrayDeque(); queue.offer(new int[]{i, j}); grid[i][j] 0; while (!queue.isEmpty()) { int[] cur queue.poll(); for (int[] d : dirs) { int ni cur[0] d[0]; int nj cur[1] d[1]; if (ni 0 ni rows nj 0 nj cols grid[ni][nj] 1) { grid[ni][nj] 0; queue.offer(new int[]{ni, nj}); } } } } } } return count; } }从代码结构上看BFS 版本和显式栈 DFS 版本几乎一模一样唯一的区别就是把栈换成了队列把push/pop换成了offer/poll。这一点非常有意思——在网格搜索里DFS 和 BFS 的骨架是通用的区别只在于用哪种数据结构来控制遍历顺序。从性能上说BFS 不会遇到递归栈溢出问题而且寻找最短路径类的问题它也更合适。这道题不存在“最短”的概念所以 DFS 和 BFS 都可但如果你后续要做 LeetCode 994 腐烂的橘子那种需要计算扩散时间的题BFS 几乎是标准答案。3.2 与 994 腐烂的橘子对比网格 BFS 的通用模板LeetCode 994 腐烂的橘子跟岛屿数量一样都属于网格 BFS 的范畴。我把两题放在一起对比是因为它们解题骨架几乎相同但有两个关键差异起始点数量和层数统计方式。在 994 题里一开始可能有好几个腐烂的橘子它们会同时向四周扩散这叫“多源 BFS”。实现时你需要先遍历一遍整个网格把所有腐烂的橘子初始状态一次性入队而不是碰到一个就启动一次搜索。而在 200 题里每遇到一个未访问的 1 才启动一次 BFS每次 BFS 对应一座岛屿。另外 994 题要统计“多少分钟后所有橘子都腐烂”所以你需要在 BFS 过程中记录层数。常用做法是每次循环时先取size queue.size()然后只处理这一层的节点处理完一层minutes。这个按层遍历的技巧后来在二叉树层序遍历、迷宫最短路径等很多题目里都会用到。这里我整理了一个简表方便你对照记忆对比维度200. 岛屿数量994. 腐烂的橘子起点个数每个岛屿一个起点启动多次 BFS所有坏橘子同时入队启动一次 BFS是否统计轮数不统计只统计启动次数需要按层统计扩散时间搜索目标找连通分量个数找所有节点被覆盖的最短时间状态标记1 改成 0 表示已访问新鲜橘子变腐同时记录时间结束条件队列为空即处理完一座岛队列为空后再检查是否有剩余新鲜橘子把这两道题连着刷一遍网格 BFS 的底子就非常扎实了。很多刷题指南里把它们排在前后脚不是没有道理的。4. 并查集与优化细节4.1 并查集思路合并相邻陆地统计根的数量DFS 和 BFS 是“染色”的思路并查集则是“合并”的思路把所有相邻的1通过union操作合并到同一个集合里最后数一数有多少个集合答案就是岛屿数量。我第一次看到并查集解法时觉得这个思路非常优雅——它不通过搜索去遍历整座岛而是通过“撮合邻居”的方式把陆地慢慢聚成团。并查集天然支持动态合并如果以后网格数据是持续更新的这种方案的优势会非常明显。实现步骤分三步。第一步二维坐标转一维编号index row * cols col。第二步统计网格中1的个数作为并查集的初始集合数count。第三步遍历每个1只看向右边和下面两个邻居避免重复合并如果邻居也是1就执行union合并成功则count--。最后返回count。这里为什么要设置一个虚拟的“水节点”我先说结论可以不设直接统计初始的 1 的数量然后每成功合并一次就减一。但为了思路统一很多并查集题解会把所有0归到一个虚拟节点上这样最后统计根节点数量时忽略虚拟节点即可。不过对于这个题直接维护count更简洁。Java 实现如下class Solution { private int[] parent; private int[] rank; public int numIslands(char[][] grid) { if (grid null || grid.length 0) { return 0; } int rows grid.length; int cols grid[0].length; parent new int[rows * cols]; rank new int[rows * cols]; int count 0; for (int i 0; i rows; i) { for (int j 0; j cols; j) { if (grid[i][j] 1) { int idx i * cols j; parent[idx] idx; count; } } } for (int i 0; i rows; i) { for (int j 0; j cols; j) { if (grid[i][j] 1) { int idx i * cols j; if (i 1 rows grid[i 1][j] 1) { if (union(idx, (i 1) * cols j)) { count--; } } if (j 1 cols grid[i][j 1] 1) { if (union(idx, i * cols j 1)) { count--; } } } } } return count; } private int find(int x) { if (parent[x] ! x) { parent[x] find(parent[x]); } return parent[x]; } private boolean union(int x, int y) { int rootX find(x); int rootY find(y); if (rootX rootY) { return false; } if (rank[rootX] rank[rootY]) { parent[rootX] rootY; } else if (rank[rootX] rank[rootY]) { parent[rootY] rootX; } else { parent[rootY] rootX; rank[rootX]; } return true; } }并查集里两个关键操作find负责查找根节点这里用了路径压缩在递归返回时把沿途节点直接指向根后续查找会越来越快union负责合并两个集合这里用了按秩合并把小树接到大树下控制整棵树的高度。路径压缩加按秩合并能让单次操作的时间复杂度降到接近常数级别整体复杂度可以认为是 O(mn × α(mn))α是反阿克曼函数在实际场景中不会超过 4。空间上需要开两个一维数组parent和rank总长度是rows * cols所以空间复杂度 O(mn)。比 DFS/BFS 多了一些内存但换来了动态扩展能力。4.2 空间优化与一个容易被追问的面试细节这里我想单独聊一个面试里几乎必被追问的点如果你直接修改了输入网格把1改成0省下了一个visited数组空间复杂度从 O(mn) 降到了 O(1)这事到底好不好先说结论。在 LeetCode 上这么写完全没问题还能让代码更简洁。但到了工程环境直接修改入参往往是大忌——这份网格数据可能是一个地图服务里共享的数据还有其他模块要读你为了算岛屿数量把它改空了别人拿到手的数据就坏了。所以在面试时我建议你主动说清楚“我默认允许修改输入所以直接原地标记。如果业务上不允许污染原始数据我可以加一个visited布尔数组区别只是空间换时间。”这一句话透露出的工程意识在很多面试官眼里比代码本身还值钱。我在实际项目里处理过类似的数据清洗问题深知“入参只读不写”这条潜规则有多重要所以即使在刷题阶段也建议你养成这个习惯——先把两种方案都说清楚再根据场景选择。5. 常见问题与排查技巧实录5.1 我踩过的五个坑一次性给你列全这道题我做过的次数绝对不少了但每次重新写还是能在评论区看到有人踩这些坑。我把自己踩过的和看到别人踩过的问题整理成一个速查表每个都写了排查思路。症状可能原因排查与解决答案比预期大很多把1当成了数字 1 判断网格是字符数组必须写grid[i][j] 1别用 1判断越界时数组越界异常边界判断写在访问格子之后先判断 i0死循环或栈溢出递归没有先标记已访问进入格子后立刻改成0不要等递归返回再改答案偏小遍历时遇到1没计数就扩散双层循环里遇到未访问1要先count再启动搜索超大网格直接崩溃递归深度过大Python 默认递归深度只有 1000换显式栈或 BFS第一个坑真的是经典中的经典。LeetCode 给的输入是char[][]字符1的底层 ASCII 码是 49如果你写成grid[i][j] 1它会拿 49 和 1 比永远不相等结果整个程序一个岛屿都找不到。我当年第一次用 C 刷题时就栽在这上面排查了快二十分钟才发现是引号的问题。第五个坑也比较隐蔽。很多人在本地跑小规模测试没问题一提交就报栈溢出还以为是 LeetCode 判题系统的问题。其实纯粹就是递归深度超过了语言默认限制。Python 里可以用sys.setrecursionlimit()临时调大但这属于治标不治本真正稳妥的还是迭代写法。5.2 面试现场怎么答才加分如果说前面讲的是“把题做对”那这一节讲的就是“把题讲好”。面试跟刷题是两码事LeetCode 题解里你只要把代码贴出来跑通就行但面试官需要看到你的思考过程。开场先说题目本质把二维网格看作图岛屿数量就是连通分量数量所以核心任务变成了“标记已访问”。然后给复杂度分析时间 O(mn)因为每个格子最多被访问常数次空间的话递归 DFS 最坏 O(mn) 递归栈BFS 最坏队列也可能到 O(mn)但如果原地改数组辅助空间可以做到 O(1)递归栈除外。说完思路以后主动补充边界情况空网格返回 0只有单个格子的网格看它是陆地还是水。再主动提一句“这道题和 994 腐烂的橘子很像那题是多源 BFS需要统计层数”面试官往往就会顺着你的思路追问这时候你就掌握了对话节奏。最后一招用实际场景解释这个算法的意义。图像处理里的连通域标记就是把每个像素当成格子统计有多少块颜色相同的区域地图应用里计算一个湖泊被多少块陆地包围本质也是网格搜索。能把算法跟真实世界连接起来说明你是真的理解而不是背模板。写在最后这道题值得做的三个理由我个人刷题有个习惯一道题做完之后会问自己这题值不值得我花时间做第二遍200 岛屿数量答案是值得而且我建议你三刷。第一遍用递归 DFS 建立直觉第二遍用 BFS 和显式栈 DFS 理解遍历顺序的本质差别第三遍试试并查集体会“合并不搜索”的新思路。三遍下来你不只是会这一道题而是把网格搜索这一类题的基础彻底打牢了。另外再分享一个小技巧做这种网格题先把方向数组{{1,0},{-1,0},{0,1},{0,-1}}写在最上面能省掉大量重复的坐标加减代码。我在后来的扫雷、单词搜索、腐烂的橘子、迷宫问题里都用到了这个习惯实测下来代码整洁度和出错率都明显改善。刷题这条路没有捷径但把经典题吃透绝对是最省时间的捷径。
LeetCode 200题岛屿数量：DFS、BFS、并查集三种解法与避坑指南
说起 LeetCode 上那些“刷题必遇”的经典题200. 岛屿数量绝对排得上前五。不管你是准备实习、秋招、春招还是单纯想把手里的 DFS、BFS 底子打牢这道题都绕不开。它在 LeetCode 热门 100 题里稳稳占了一个位置也是各大厂面试里出现频率极高的网格搜索题。这道题最妙的地方在于它不考什么高级技巧也不需要复杂的数学推导只要你理解“连通分量”这个概念会写最基础的深度优先或广度优先搜索就能给出一个面试官认可的标准答案。但反过来它考察的细节非常多——字符和数字的区分、边界检查的顺序、递归深度带来的栈溢出风险、要不要修改原始数据……每个点都能展开聊一聊。这篇文章我就以自己做这道题的实际经验为主线把 DFS、BFS、并查集三种思路都拆开揉碎了讲一遍再把平时容易被忽略的坑全部列出来。1. 题目本质与破题思路1.1 题面到底在说什么题目给你一个二维网格里面只有两种字符1代表陆地0代表水。岛屿的定义是“被水包围的、连续相邻的陆地区域”。这里的“相邻”有明确限定只能是上下左右四个方向斜对角不算。也就是说上面是 1、下面是 1、左边是 1、右边是 1 这样连成一片的才叫同一块岛屿。如果只是斜着碰到算两块独立的岛。举个最经典的例子网格是11110 11010 11000 00000左上角那五块 1 全部连在一起构成一个岛屿。虽然中间有个 0但 0 只是把右上角的 1 隔开了。右下角的 1 没有与任何其他 1 四方向相邻所以它是独立的一个岛屿。于是答案就是 2。另一个例子更直观11000 11000 00100 00011三块互不相连的陆地答案 3。核心就一句话数一数整个网格里有几个连通的陆地集团。1.2 破题核心把问题转化为连通分量计数如果你以前接触过图论其实一眼就能看出来——这个二维网格本质上就是一张图每个格子是一个节点上下左右相邻的格子之间有一条边。而岛屿的数量就是这张图中“值为 1 的节点”构成的连通分量的个数。连通分量的定义很简单在一个无向图里如果若干个节点彼此之间能通过边到达它们就在同一个连通分量里互相到不了的就是不同的分量。放到这个题目里同一座岛就是同一个连通分量。所以解题思路就变得很清晰遍历整个网格每次遇到一个没访问过的1就说明发现了一个新岛屿计数器加 1然后从它出发把所有跟它相连的1全部标记为“已访问”。这样下次遍历到它们时就不会再重复计数。这个“标记已访问”的动作可以用深度优先搜索DFS做可以用广度优先搜索BFS做也可以用并查集把所有相邻的 1 合并起来最后数一数有几个集合。三种方案殊途同归但各有各的适用场景。1.3 为什么它是 LeetCode 热搜榜单的常客说点刷题圈子里大家心照不宣的事LeetCode 热门 100 题里的题目几乎每道都对应着一类核心算法范式。像 073 爱吃香蕉的狒狒是二分答案的经典基本计算器是栈和表达式解析的经典而 200 岛屿数量就是图论搜索的入门必刷题。这道题能火这么多年我真的一点都不意外。它表面上是一道题实际上承担了三个功能第一它是你理解网格类 DFS/BFS 的敲门砖以后的扫雷游戏、迷宫寻路、腐烂的橘子全都从这个模板延伸出去第二它在面试里特别好使一个候选人会不会写边界检查、能不能分析递归栈、有没有意识到数据污染问题两三分钟就能看出来第三它跟真实世界的很多问题直接挂钩——图像处理里的连通域标记、地图上的湖泊岛屿统计、社交网络里的群组划分核心都是同一套逻辑。所以别觉得这题简单就不认真对待把它的每一个细节吃透后面的网格题你会走得很顺。2. DFS直觉解法的两种实现2.1 递归写法三句话搞定主逻辑DFS 是大多数人看到这道题的第一反应因为思路最贴合直觉发现一个岛就往四面八方扎进去把能走到的陆地全走一遍走不动了再回来。先看完整的 Java 递归解法class Solution { public int numIslands(char[][] grid) { if (grid null || grid.length 0) { return 0; } int rows grid.length; int cols grid[0].length; int count 0; for (int i 0; i rows; i) { for (int j 0; j cols; j) { if (grid[i][j] 1) { count; dfs(grid, i, j); } } } return count; } private void dfs(char[][] grid, int i, int j) { int rows grid.length; int cols grid[0].length; if (i 0 || i rows || j 0 || j cols || grid[i][j] 0) { return; } grid[i][j] 0; dfs(grid, i - 1, j); dfs(grid, i 1, j); dfs(grid, i, j - 1); dfs(grid, i, j 1); } }主函数里套一个双层循环碰到1就计数加 1然后调用dfs把这座岛“淹没”。这里的淹没就是把1改成0相当于标记已访问。dfs里的逻辑也简单先判断越界和当前格子是不是水如果是就返回如果当前格子是陆地立刻把它改成0再往上下左右四个方向递归。这里有几个细节我必须强调一下。第一边界检查的顺序很有讲究i 0 || i rows || j 0 || j cols这个判断必须放在最前面避免数组越界访问。第二判断必须是grid[i][j] 0而不是grid[i][j] ! 1虽然在这个题里结果一样但如果你把输入数据当成整数数组来做就会踩坑这个我后面专门讲。第三把当前格子改成0一定要在递归之前这叫“先标记后扩散”防止在递归过程中重复访问同一个格子否则会产生死循环。如果换用 Python代码更短核心思路完全一致class Solution: def numIslands(self, grid: List[List[str]]) - int: if not grid: return 0 m, n len(grid), len(grid[0]) def dfs(i, j): if i 0 or i m or j 0 or j n or grid[i][j] 0: return grid[i][j] 0 dfs(i - 1, j) dfs(i 1, j) dfs(i, j - 1) dfs(i, j 1) ans 0 for i in range(m): for j in range(n): if grid[i][j] 1: ans 1 dfs(i, j) return ans2.2 递归深度风险什么情况下必须换显式栈递归版本够简单但我要泼一盆冷水当你真正在刷题平台上提交或者在实际项目里遇到超大网格时递归深度可能成为最大的隐患。这道题目的输入约束通常是 300 × 300 以内理论上递归深度最多 90000 层。但 Java 默认的虚拟机栈深度通常只有几千到一万多层Python 的默认递归深度更是只有 1000 层。一旦网格全部是1DFS 一路扎进去可能直接触发StackOverflowError或RecursionError。我第一次在本地用 Python 跑一个 200 × 200 的全 1 网格时就遇到了递归深度超限。当时我还以为是代码写错了排查了半天才发现是递归层数的问题。所以在面试场景里如果你主动跟面试官讨论这个问题说“递归版本思路清晰但存在栈溢出风险我可以改成显式栈”这绝对是个加分项。显式栈版本是这样写的class Solution { public int numIslands(char[][] grid) { if (grid null || grid.length 0) { return 0; } int rows grid.length; int cols grid[0].length; int count 0; int[][] dirs {{1, 0}, {-1, 0}, {0, 1}, {0, -1}}; for (int i 0; i rows; i) { for (int j 0; j cols; j) { if (grid[i][j] 1) { count; Dequeint[] stack new ArrayDeque(); stack.push(new int[]{i, j}); grid[i][j] 0; while (!stack.isEmpty()) { int[] cur stack.pop(); for (int[] d : dirs) { int ni cur[0] d[0]; int nj cur[1] d[1]; if (ni 0 ni rows nj 0 nj cols grid[ni][nj] 1) { grid[ni][nj] 0; stack.push(new int[]{ni, nj}); } } } } } } return count; } }注意几个细节用ArrayDeque当栈比Stack类性能好每次把新节点压栈前就立刻标记为0而不是弹出时才标记这是避免重复入栈的关键方向数组dirs让四个方向的扩展代码变得非常简洁。实测下来显式栈在超大网格上的稳定性比递归好得多代码量增加的也有限。如果你在 LeetCode 上做题我建议至少动手写一遍这个版本因为它能帮你真正理解 DFS 的本质——显式栈模拟了系统递归栈的行为。3. BFS 与变形题实战3.1 标准 BFS一层一层地“感染”DFS 是“一条路走到黑”BFS 则是“一圈一圈往外扩”。思路同样直接发现一个陆地1把它作为起点放进队列然后一层一层地把周围的 1 全部感染成 0直到队列为空说明这一整座岛都被处理完了。class Solution { public int numIslands(char[][] grid) { if (grid null || grid.length 0) { return 0; } int rows grid.length; int cols grid[0].length; int count 0; int[][] dirs {{1, 0}, {-1, 0}, {0, 1}, {0, -1}}; for (int i 0; i rows; i) { for (int j 0; j cols; j) { if (grid[i][j] 1) { count; Queueint[] queue new ArrayDeque(); queue.offer(new int[]{i, j}); grid[i][j] 0; while (!queue.isEmpty()) { int[] cur queue.poll(); for (int[] d : dirs) { int ni cur[0] d[0]; int nj cur[1] d[1]; if (ni 0 ni rows nj 0 nj cols grid[ni][nj] 1) { grid[ni][nj] 0; queue.offer(new int[]{ni, nj}); } } } } } } return count; } }从代码结构上看BFS 版本和显式栈 DFS 版本几乎一模一样唯一的区别就是把栈换成了队列把push/pop换成了offer/poll。这一点非常有意思——在网格搜索里DFS 和 BFS 的骨架是通用的区别只在于用哪种数据结构来控制遍历顺序。从性能上说BFS 不会遇到递归栈溢出问题而且寻找最短路径类的问题它也更合适。这道题不存在“最短”的概念所以 DFS 和 BFS 都可但如果你后续要做 LeetCode 994 腐烂的橘子那种需要计算扩散时间的题BFS 几乎是标准答案。3.2 与 994 腐烂的橘子对比网格 BFS 的通用模板LeetCode 994 腐烂的橘子跟岛屿数量一样都属于网格 BFS 的范畴。我把两题放在一起对比是因为它们解题骨架几乎相同但有两个关键差异起始点数量和层数统计方式。在 994 题里一开始可能有好几个腐烂的橘子它们会同时向四周扩散这叫“多源 BFS”。实现时你需要先遍历一遍整个网格把所有腐烂的橘子初始状态一次性入队而不是碰到一个就启动一次搜索。而在 200 题里每遇到一个未访问的 1 才启动一次 BFS每次 BFS 对应一座岛屿。另外 994 题要统计“多少分钟后所有橘子都腐烂”所以你需要在 BFS 过程中记录层数。常用做法是每次循环时先取size queue.size()然后只处理这一层的节点处理完一层minutes。这个按层遍历的技巧后来在二叉树层序遍历、迷宫最短路径等很多题目里都会用到。这里我整理了一个简表方便你对照记忆对比维度200. 岛屿数量994. 腐烂的橘子起点个数每个岛屿一个起点启动多次 BFS所有坏橘子同时入队启动一次 BFS是否统计轮数不统计只统计启动次数需要按层统计扩散时间搜索目标找连通分量个数找所有节点被覆盖的最短时间状态标记1 改成 0 表示已访问新鲜橘子变腐同时记录时间结束条件队列为空即处理完一座岛队列为空后再检查是否有剩余新鲜橘子把这两道题连着刷一遍网格 BFS 的底子就非常扎实了。很多刷题指南里把它们排在前后脚不是没有道理的。4. 并查集与优化细节4.1 并查集思路合并相邻陆地统计根的数量DFS 和 BFS 是“染色”的思路并查集则是“合并”的思路把所有相邻的1通过union操作合并到同一个集合里最后数一数有多少个集合答案就是岛屿数量。我第一次看到并查集解法时觉得这个思路非常优雅——它不通过搜索去遍历整座岛而是通过“撮合邻居”的方式把陆地慢慢聚成团。并查集天然支持动态合并如果以后网格数据是持续更新的这种方案的优势会非常明显。实现步骤分三步。第一步二维坐标转一维编号index row * cols col。第二步统计网格中1的个数作为并查集的初始集合数count。第三步遍历每个1只看向右边和下面两个邻居避免重复合并如果邻居也是1就执行union合并成功则count--。最后返回count。这里为什么要设置一个虚拟的“水节点”我先说结论可以不设直接统计初始的 1 的数量然后每成功合并一次就减一。但为了思路统一很多并查集题解会把所有0归到一个虚拟节点上这样最后统计根节点数量时忽略虚拟节点即可。不过对于这个题直接维护count更简洁。Java 实现如下class Solution { private int[] parent; private int[] rank; public int numIslands(char[][] grid) { if (grid null || grid.length 0) { return 0; } int rows grid.length; int cols grid[0].length; parent new int[rows * cols]; rank new int[rows * cols]; int count 0; for (int i 0; i rows; i) { for (int j 0; j cols; j) { if (grid[i][j] 1) { int idx i * cols j; parent[idx] idx; count; } } } for (int i 0; i rows; i) { for (int j 0; j cols; j) { if (grid[i][j] 1) { int idx i * cols j; if (i 1 rows grid[i 1][j] 1) { if (union(idx, (i 1) * cols j)) { count--; } } if (j 1 cols grid[i][j 1] 1) { if (union(idx, i * cols j 1)) { count--; } } } } } return count; } private int find(int x) { if (parent[x] ! x) { parent[x] find(parent[x]); } return parent[x]; } private boolean union(int x, int y) { int rootX find(x); int rootY find(y); if (rootX rootY) { return false; } if (rank[rootX] rank[rootY]) { parent[rootX] rootY; } else if (rank[rootX] rank[rootY]) { parent[rootY] rootX; } else { parent[rootY] rootX; rank[rootX]; } return true; } }并查集里两个关键操作find负责查找根节点这里用了路径压缩在递归返回时把沿途节点直接指向根后续查找会越来越快union负责合并两个集合这里用了按秩合并把小树接到大树下控制整棵树的高度。路径压缩加按秩合并能让单次操作的时间复杂度降到接近常数级别整体复杂度可以认为是 O(mn × α(mn))α是反阿克曼函数在实际场景中不会超过 4。空间上需要开两个一维数组parent和rank总长度是rows * cols所以空间复杂度 O(mn)。比 DFS/BFS 多了一些内存但换来了动态扩展能力。4.2 空间优化与一个容易被追问的面试细节这里我想单独聊一个面试里几乎必被追问的点如果你直接修改了输入网格把1改成0省下了一个visited数组空间复杂度从 O(mn) 降到了 O(1)这事到底好不好先说结论。在 LeetCode 上这么写完全没问题还能让代码更简洁。但到了工程环境直接修改入参往往是大忌——这份网格数据可能是一个地图服务里共享的数据还有其他模块要读你为了算岛屿数量把它改空了别人拿到手的数据就坏了。所以在面试时我建议你主动说清楚“我默认允许修改输入所以直接原地标记。如果业务上不允许污染原始数据我可以加一个visited布尔数组区别只是空间换时间。”这一句话透露出的工程意识在很多面试官眼里比代码本身还值钱。我在实际项目里处理过类似的数据清洗问题深知“入参只读不写”这条潜规则有多重要所以即使在刷题阶段也建议你养成这个习惯——先把两种方案都说清楚再根据场景选择。5. 常见问题与排查技巧实录5.1 我踩过的五个坑一次性给你列全这道题我做过的次数绝对不少了但每次重新写还是能在评论区看到有人踩这些坑。我把自己踩过的和看到别人踩过的问题整理成一个速查表每个都写了排查思路。症状可能原因排查与解决答案比预期大很多把1当成了数字 1 判断网格是字符数组必须写grid[i][j] 1别用 1判断越界时数组越界异常边界判断写在访问格子之后先判断 i0死循环或栈溢出递归没有先标记已访问进入格子后立刻改成0不要等递归返回再改答案偏小遍历时遇到1没计数就扩散双层循环里遇到未访问1要先count再启动搜索超大网格直接崩溃递归深度过大Python 默认递归深度只有 1000换显式栈或 BFS第一个坑真的是经典中的经典。LeetCode 给的输入是char[][]字符1的底层 ASCII 码是 49如果你写成grid[i][j] 1它会拿 49 和 1 比永远不相等结果整个程序一个岛屿都找不到。我当年第一次用 C 刷题时就栽在这上面排查了快二十分钟才发现是引号的问题。第五个坑也比较隐蔽。很多人在本地跑小规模测试没问题一提交就报栈溢出还以为是 LeetCode 判题系统的问题。其实纯粹就是递归深度超过了语言默认限制。Python 里可以用sys.setrecursionlimit()临时调大但这属于治标不治本真正稳妥的还是迭代写法。5.2 面试现场怎么答才加分如果说前面讲的是“把题做对”那这一节讲的就是“把题讲好”。面试跟刷题是两码事LeetCode 题解里你只要把代码贴出来跑通就行但面试官需要看到你的思考过程。开场先说题目本质把二维网格看作图岛屿数量就是连通分量数量所以核心任务变成了“标记已访问”。然后给复杂度分析时间 O(mn)因为每个格子最多被访问常数次空间的话递归 DFS 最坏 O(mn) 递归栈BFS 最坏队列也可能到 O(mn)但如果原地改数组辅助空间可以做到 O(1)递归栈除外。说完思路以后主动补充边界情况空网格返回 0只有单个格子的网格看它是陆地还是水。再主动提一句“这道题和 994 腐烂的橘子很像那题是多源 BFS需要统计层数”面试官往往就会顺着你的思路追问这时候你就掌握了对话节奏。最后一招用实际场景解释这个算法的意义。图像处理里的连通域标记就是把每个像素当成格子统计有多少块颜色相同的区域地图应用里计算一个湖泊被多少块陆地包围本质也是网格搜索。能把算法跟真实世界连接起来说明你是真的理解而不是背模板。写在最后这道题值得做的三个理由我个人刷题有个习惯一道题做完之后会问自己这题值不值得我花时间做第二遍200 岛屿数量答案是值得而且我建议你三刷。第一遍用递归 DFS 建立直觉第二遍用 BFS 和显式栈 DFS 理解遍历顺序的本质差别第三遍试试并查集体会“合并不搜索”的新思路。三遍下来你不只是会这一道题而是把网格搜索这一类题的基础彻底打牢了。另外再分享一个小技巧做这种网格题先把方向数组{{1,0},{-1,0},{0,1},{0,-1}}写在最上面能省掉大量重复的坐标加减代码。我在后来的扫雷、单词搜索、腐烂的橘子、迷宫问题里都用到了这个习惯实测下来代码整洁度和出错率都明显改善。刷题这条路没有捷径但把经典题吃透绝对是最省时间的捷径。
