1. 岛屿数量这道题到底在考什么今天聊的这道「岛屿数量」是 LeetCode 第 200 题也是所有算法题库里最经典的图论入门题之一。题目本身并不复杂给你一个二维网格里面是1陆地和0水要求统计岛屿的数量。所谓岛屿就是由上下左右相邻的陆地连成的一片区域斜对角不算连通。先说我第一次刷这道题时的一个感受题目简单归简单但它几乎覆盖了图遍历的所有核心思路——深度优先搜索、广度优先搜索、连通分量统计、原地标记状态甚至进阶解法里还能引入并查集。换句话说这道题看似只是在数岛屿实际上是在考察你对如何遍历一张图如何避免重复访问如何统计连通块这三个问题的理解程度。面试时遇到它考的不是你会不会写递归而是你能不能把三种主流解法都讲明白并且说清楚各自的适用场景和复杂度差异。这道题的另一个价值在于它是大量更高阶题目的一块跳板。你后面会遇到岛屿最大面积、岛屿周长、不同岛屿数量、被围绕的区域、墙与门等等基本都是在这道题的基础上加限制条件或者换统计口径。把这道题吃透等于把一组同源问题的内核抓住了。2. 深度优先搜索解法把整座岛淹掉最省事2.1 核心思想和代码实现DFS 的思路非常直白遍历整个网格当遇到一个1时说明发现了一座新岛屿计数器加一接下来从这个格子出发沿着上下左右四个方向一直走凡是能走到的1都把它改成0这就是淹没。等这轮递归结束整座岛已经被清零了继续往后遍历不会重复计数。def numIslands(grid): if not grid or not grid[0]: return 0 rows, cols len(grid), len(grid[0]) count 0 def dfs(r, c): # 超出边界或者当前不是陆地直接返回 if r 0 or r rows or c 0 or c cols or grid[r][c] 0: return grid[r][c] 0 # 标记为已访问防止重复遍历 dfs(r - 1, c) # 上 dfs(r 1, c) # 下 dfs(r, c - 1) # 左 dfs(r, c 1) # 右 for r in range(rows): for c in range(cols): if grid[r][c] 1: count 1 dfs(r, c) return count这里最关键的细节就是grid[r][c] 0这一行。没有它递归会无限循环——因为相邻的格子互相看到对方是1会一直互相调用。我见过不少人在初学阶段漏掉这一步然后陷入栈溢出。标记的方式除了改成0也可以用 visited 集合单独记录但那样会多 O(MN) 的空间而且代码反而更啰嗦。直接在原数组上改是这类题最常见的做法面试时也最容易讲清楚。2.2 复杂度与递归深度问题时间复杂度是 O(M×N)因为每个格子最多被访问一次空间复杂度在网格全是陆地的最坏情况下是 O(M×N)——递归栈的深度会被压到所有格子数量。这里有一个实际工程中值得注意的点如果网格非常大比如 10000×10000 的矩阵这种递归写法在语言默认栈大小下很可能直接爆栈。我自己在牛客和 LeetCode 上刷这题时 Python 递归没出过问题但如果你把这个思路搬到实际项目里去处理超大栅格数据建议用下面要讲的 BFS或者把 DFS 改成显式栈来模拟递归。面试时如果被问到网格特别大怎么办能主动说出这个风险点会是一个加分表现。3. 广度优先搜索解法用队列层层扩散更稳3.1 为什么说 BFS 是面试中的稳妥牌BFS 的思路和 DFS 本质上一样遇到1计数加一然后把这块陆地的所有邻居都标记为已访问。区别在于扩散的方式——DFS 是沿着一条路走到黑再回头BFS 是像水波一样一圈一圈往外扩。实现上需要借助一个队列先把当前节点入队然后循环处理每次从队列头部弹出一个格子检查它的四个方向如果是陆地就标记并入队。from collections import deque def numIslands(grid): if not grid or not grid[0]: return 0 rows, cols len(grid), len(grid[0]) count 0 directions [(1, 0), (-1, 0), (0, 1), (0, -1)] for r in range(rows): for c in range(cols): if grid[r][c] 1: count 1 queue deque([(r, c)]) grid[r][c] 0 while queue: x, y queue.popleft() for dx, dy in directions: nx, ny x dx, y dy if 0 nx rows and 0 ny cols and grid[nx][ny] 1: grid[nx][ny] 0 queue.append((nx, ny)) return countBFS 和 DFS 在时间、空间复杂度上几乎没有差别但在递归深度受限的场景下BFS 是更稳的选择。它不需要依赖系统调用栈队列在堆上分配理论上处理更大规模的网格也不容易崩。所以在实际工作中我处理类似的连通区域标记问题时更倾向于 BFS 或显式栈 DFS而不是递归 DFS。3.2 两个容易踩的坑第一个坑是忘记在入队时标记。你可能会想弹出的时候再标记不行吗不行。如果不 push 进队列前就标记同一个格子可能被多个邻居重复入队。网格全是陆地时队列里会塞进来大量重复坐标不仅浪费时间还可能导致队列膨胀到难以接受的大小。正确的做法是入队那一刻就标记为0。第二个坑是方向数组写错。上下左右四个方向的坐标偏移分别是(1,0)、(-1,0)、(0,1)、(0,-1)。有些人写成(0,1)、(0,2)这种还没跑就发现索引越界。建议把方向数组抽出来单独定义既减少出错还能顺便提升代码可读性。多说一句BFS 解法在面试时还有一个隐藏优势它递地引出另一个考点——如果你想把每个岛屿的面积也算出来BFS 只需要在循环里加一个计数器就行而 DFS 需要额外维护一个返回值。这种从一道题延伸到另一道题的答法面试官通常很吃这一套。4. 并查集解法把问题抽象成连通分量统计4.1 并查集为什么也能解这道题DFS 和 BFS 是大多数人能想到的解法但如果你想在面试中展示更深的理解并查集Union-Find是很好的加分项。核心思路是把所有1的格子看成独立的节点相邻的陆地节点做合并操作最后统计一共有多少个连通分量这个数量就是岛屿数。并查集的好处在于它把遍历这件事彻底换了个角度——不是从某一个点出发去扩散而是把所有邻接关系逐一处理最后数一数有几个老大。这种思路在处理动态连通性问题比如不断有新的格子变成陆地时尤其有价值因为并查集天然支持高效的增量合并而 DFS/BFS 每次数据变化可能都要重新遍历整张图。4.2 Java 实现与关键细节class UnionFind { int[] parent; int count; public UnionFind(char[][] grid) { int m grid.length, n grid[0].length; parent new int[m * n]; for (int i 0; i m; i) { for (int j 0; j n; j) { int id i * n j; parent[id] id; if (grid[i][j] 1) { count; } } } } public int find(int x) { while (parent[x] ! x) { parent[x] parent[parent[x]]; // 路径压缩 x parent[x]; } return x; } public void union(int x, int y) { int rootX find(x); int rootY find(y); if (rootX ! rootY) { parent[rootX] rootY; count--; } } } public int numIslands(char[][] grid) { if (grid null || grid.length 0) return 0; int m grid.length, n grid[0].length; UnionFind uf new UnionFind(grid); int[] dx {1, -1, 0, 0}; int[] dy {0, 0, 1, -1}; for (int i 0; i m; i) { for (int j 0; j n; j) { if (grid[i][j] 1) { int id i * n j; for (int k 0; k 4; k) { int ni i dx[k], nj j dy[k]; if (ni 0 ni m nj 0 nj n grid[ni][nj] 1) { uf.union(id, ni * n nj); } } } } } return uf.count; }这里有个容易搞错的地方并查集的count初始值应该是网格中1的总数而不是网格总数。每成功合并一次连通分量减少一个。如果你把count初始成所有格子数最后还要减掉水的数量逻辑绕一圈不说还容易出错。并查集写法的代码量明显比 DFS/BFS 多面试时间紧张时不一定划算。我的建议是如果面试官要求换一种解法或者你感觉聊得比较深再掏出并查集如果只要求快速出正确解DFS 是最快路径。5. 变体题和边界条件只做一题远远不够5.1 从数岛屿到求最大岛屿面积刷完这道题直接做 LeetCode 695「岛屿的最大面积」是最自然的进阶路线。逻辑几乎一样只是把每次 DFS/BFS 扩散时经过的格子数记下来取最大值。也就是把计个数改成算面积。我当时是在同一天连刷这两题的做完之后对 DFS 的理解明显更扎实了可以试试。类似的变体还有「岛屿的周长」——不统计数量而是统计每个陆地格子贡献的边界长度。5.2 关于岛屿形状去重和被围绕的区域再往上是「不同岛屿数量」这类题要求统计形状上有区别的岛屿。做法是在遍历时记录 DFS/BFS 的路径轨迹比如上下左右分别编码成1234每次移动就把方向码拼到字符串里用哈希集合去重。还有一个常见的「被围绕的区域」题本质上也是在图上找连通分量然后把位于边界的连通分量特殊标记最后统一翻转。如果只想做三道题我个人推荐组合是岛屿数量 岛屿最大面积 岛屿周长。这三题做完你对网格类 DFS 的框架已经掌握了大半。5.3 边界条件和细节检查清单这题卡住人的地方往往不是算法思路而是一些低级但致命的细节。我列一个自己每次写都会默念的清单字符1和数字1别混。Java 里grid[i][j] 1永远不成立因为你存的是字符的编码值。Python 里1和1同样不相等。这是新手最常见的错误。空网格和空行的处理。grid为空或者grid[0]为空即一行都没有都要直接返回 0。递归/循环过程中修改原数组会改变后续遍历的条件。这是预期行为但你要清楚知道自己在改数组别误以为是在只读访问。输入很多情况下是char[][]而不是int[][]别被题目的字符表示唬住。这些边界条件我在实际写的时候往往写完主体逻辑后会再花 30 秒扫一遍避免提交之后才发现低级失误。6. 面试中怎么讲这道题以及我的刷题建议6.1 面试官想听到什么如果你在面试中遇到这道题我的建议是按照先讲思路再写代码最后分析复杂度的顺序来。首先说明你要用 DFS/BFS 遍历所有陆地遇到新的陆地就让计数器加一然后把整片区域标记为已访问。写代码的时候可以顺口解释你为什么要原地修改数组——为了省空间避免另开 visited 数组。如果面试官追问如果图特别大递归会有什么问题你可以顺势展开讲 BFS 和显式栈方案。如果面试官问如果网格里的陆地是动态增加的频繁查询岛屿数量应该怎么做这时候并查集就是标准答案。6.2 我个人刷这道题的真实体会我是在准备面试的那段时间集中刷的 LeetCode 前 200 题岛屿数量正好排在比较靠前的位置当时我用一天时间把 DFS、BFS、并查集三种解法各写了两遍第二天又用同样的方法重新做了「岛屿最大面积」。整个过程下来最明显的感受是这类网格遍历题不需要背题只需要想明白一个核心问题——如何保证访问过的节点不被重复访问。围绕这一件事DFS、BFS 和并查集三种思路都能展开。后来我在实际工作中处理过一个类似的需求给一张地图数据里的若干连通区域打标记。当时我直接参考的就是这道题的 BFS 版本把它改造成遍历二值化图像、标记连通域的工具函数处理 4000×4000 的图像没有任何压力。算法题和实际工程之间的距离很多时候比想象中要近得多。这也是我坚持每天刷一点算法的原因——不一定为了面试更多是保持对这类基础思维的敏感度。