我第一次正经刷题碰到“695岛屿最大面积”应该算是比较晚的。当时数组和链表这些基础还没完全过完看到题目里那张 0 和 1 组成的网格第一反应是这不是两层循环暴力数一下就行了吗等真动手写才发现“怎么判断相邻的 1 属于同一块陆地”“已经数过的格子怎么避免重复计数”这些看似基础的问题一旦没想清楚代码写出来就全是坑。这道题本身不难给定一个 m x n 的二维数组1 表示陆地、0 表示水水平或垂直方向相邻的 1 组成一块岛屿要求返回所有岛屿中的最大面积没有岛屿就返回 0。它本质上是一个“网格连通域”问题也是 DFS、BFS 搜索最经典的入门题。这篇文章我会从题目模型、三种解法、代码实现到容易踩的坑以及它背后能延伸出去的一串兄弟题一次性讲透。适合刚开始刷题、对递归和搜索还不熟的读者也适合想把地图类搜索题整理成体系的人。1. 先把题目模型拆明白一个二维数组就是一张图1.1 用一个更小的例子手动跑一遍官方给的是一个好几行的网格初看容易晕。我换成更小的 4 行 4 列自己手动过一遍思路立刻就清楚了。1 0 1 1 1 0 0 1 0 0 0 0 0 1 1 0左上角位置 (0,0) 和 (1,0) 上下相邻组成一块面积是 2。右上角(0,2)、(0,3)、(1,3) 这三个位置通过水平和垂直方向连在一起面积是 3。底部(3,1) 和 (3,2) 左右相邻面积是 2。最大面积就是 3。这个例子看起来简单但它其实纠正了一个常见误解题目里的“面积”并不是我们日常说的矩形面积而是“同一个连通块中的格子总数”。LeetCode 里称为 area英文描述也写得很清楚。有人第一次做这题会下意识在网格上画一个包围盒然后用长乘宽去算结果跟答案完全对不上就是这个概念没转过弯。1.2 相邻的定义是四方向不是八方向题目明确说了水平或垂直相邻才算同一块。也就是说两个格子如果只是在斜对角方向碰了一下不算同一座岛。比如一张网格里 (0,0) 是 1(1,1) 也是 1但 (0,0) 和 (1,1) 之间既没有共同边也没有路径那它们就是两座独立的岛屿。很多初学者在写方向数组的时候会不自觉地把四个方向扩成八个方向多算了左上、右上、左下、右下。这样做的后果很直接原本两座不相连的岛被你强行拼成一座面积直接翻倍。如果你之前接触过图像处理里的连通区域标记可能会遇到 8 连通的概念那是另一套规则。不同的题目有不同的定义刷 LeetCode 的岛屿系列时先确认题目说的是 4 连通还是 8 连通永远是一个好习惯。695 里只用四个方向上、下、左、右。1.3 网格本身就是一种图的存储方式第一次接触图论的人总以为图一定要写成邻接表或者邻接矩阵。其实二维网格本身就是一种图每个格子是一个节点相邻关系就是边1 表示这个节点存在0 表示不存在。找岛屿本质上就是找出这个图里的所有连通分量并统计每个连通分量的规模。想通这一点后面很多题都能统一起来。比如你之后做岛屿数量、岛屿周长、被围绕的区域会发现代码骨架几乎一样差别只在搜索入口和统计方式。这也是为什么我推荐把 695 当作模板题来做它的数据是规则的网格不需要建图坐标本身就是节点省掉了一大截抽象成本。你只需要专注理解 DFS 和 BFS 的核心逻辑而不是纠结“这个图到底怎么存”。2. 动手之前的选择DFS、BFS、并查集能解但气质不同2.1 DFS顺着一条路走到黑再回头DFS 的思想用一句话说从一个陆地格子出发标记它已经被访问过然后向上下左右四个方向继续探索遇到水或越界就停下遇到没访问过的陆地就继续递归。拿生活场景类比你在一片空地上泼一桶水水会顺着每一条通道往前流流到尽头再回溯最后所有被水浸湿的格子就是同一块区域。这个“浸湿”的动作就是标记访问。在 695 里DFS 的返回值可以直接设计成面积当前格子本身算 1再加上四个方向递归返回的面积。代码层面非常优雅不需要额外维护一个计数器。我在下面会给你完整实现这种“1 四个方向的递归结果”的写法比在外面定义一个变量累加要清晰得多也不容易漏重置。2.2 BFS一层一层向外扩散BFS 的思想是使用队列从一个陆地格子出发把它放进队列然后循环弹出队首格子扩展它的四个方向把相邻的陆地格子继续放进队列。队列空了说明这一整块岛屿都访问完了。类比一下更像一个消息从原点向外一层层扩散每一轮扩散把所有“新感染”的格子放进队列尾部。BFS 的好处是迭代实现没有递归调用所以不存在递归深度过大导致爆栈的问题。代价是代码比 DFS 长一点需要显式维护一个队列。2.3 并查集把合并关系变成集合关系第三种思路是并查集看问题的角度完全不同每个 1 格子一开始都是独立的“小岛”面积都是 1。然后遍历网格碰到相邻的 1 就把它们合并成一个集合同时把面积累加到根节点上。最后扫描所有格子找出面积最大的根节点。并查集在静态网格上看起来有点“杀鸡用牛刀”但它的价值在于可以处理动态合并的场景。比如 LeetCode 827 最大人工岛允许你把某个 0 改成 1然后再求最大岛屿面积这类题用并查集的视野会舒服很多。并查集的关键操作就两个find 找根节点union 合并两个集合。如果希望合并后快速知道每个集合的规模就额外维护一个 size 数组合并时把子集的 size 加到父集上。核心代码片段大概是这样的class DSU: def __init__(self, n): self.parent list(range(n)) self.size [1] * n def find(self, x): while self.parent[x] ! x: self.parent[x] self.parent[self.parent[x]] x self.parent[x] return x def union(self, a, b): ra, rb self.find(a), self.find(b) if ra rb: return if self.size[ra] self.size[rb]: ra, rb rb, ra self.parent[rb] ra self.size[ra] self.size[rb]然后在主循环里把二维坐标映射成一维索引i * n j每个 1 格子只和右侧、下侧的邻居合并。这样每条相邻边只会被处理一次不会重复。2.4 三种方案对比与选择方案核心依赖时间复杂度空间复杂度优点注意点DFS递归 / 系统栈O(m*n)O(m*n) 递归栈代码最短语义最贴切递归深度可能超限BFS显式队列O(m*n)O(m*n) 队列空间迭代实现不易爆栈代码略长要小心重复入队并查集父子数组O(mnα)O(m*n)可扩展动态合并场景抽象度更高第一次接触要适应我的建议是第一次做这道题优先掌握 DFS因为代码最直观也最容易讲清楚思路。但心里要对 BFS 和并查集两个版本有概念。面试时如果考官追问“网格特别大、递归爆栈了怎么办”你能立刻切换到 BFS 或者显式栈会非常加分。3. 从思路到代码以 DFS 为主线写一遍标准解3.1 主循环与递归函数的分工整套代码只有两个部分。第一部分是主循环遍历整个网格如果当前格子是 1 且没有被访问过就把它当作一座岛屿的起点调用递归函数把这个连通块全部扫一遍。每个新扫出来的面积都去更新全局最大值。第二部分是递归函数给定一个坐标 (i, j)先判断越界、是否是陆地、是否已经访问过。如果条件都不满足就标记已访问然后递归处理四个方向。返回值是当前格子 1 加上四个方向的递归结果。这个分工模式几乎是所有网格搜索题的万能骨架。后面做岛屿数量、岛屿周长改的都是这两部分里的统计逻辑整体结构不会变。3.2 两个关键实现细节标记与返回值第一个坑是标记已访问。最常用的两种方式维护一个独立的 visited 二维数组初始全是 False访问过就置为 True。直接修改原数组把已经访问过的 1 改成 0这种技巧常叫“淹没法”或“沉岛法”。如果面试或者在真实工程项目里我更推荐 visited 数组原因很简单它不破坏原始输入。有些场景里 grid 后续还要复用你直接改成 0 之后数据就丢了。但 LeetCode 刷题无所谓很多人喜欢淹没法因为代码更短。两种都要会我下面都会给你。第二个细节是统计面积的方式。用返回值比用全局变量舒服很多。如果你在外面定义一个area在递归里area 1那每次从新起点开始之前都必须记得把area重置成 0。一旦忘了重置结果会累加上一轮的数据。用返回值的话每个递归子问题各自返回自己的面积逻辑天然闭合不容易出错。3.3 Python 标准实现visited 版本from typing import List class Solution: def maxAreaOfIsland(self, grid: List[List[int]]) - int: if not grid or not grid[0]: return 0 m, n len(grid), len(grid[0]) visited [[False] * n for _ in range(m)] best 0 def dfs(i: int, j: int) - int: if i 0 or i m or j 0 or j n: return 0 if grid[i][j] 0 or visited[i][j]: return 0 visited[i][j] True return ( 1 dfs(i 1, j) dfs(i - 1, j) dfs(i, j 1) dfs(i, j - 1) ) for i in range(m): for j in range(n): if grid[i][j] 1 and not visited[i][j]: best max(best, dfs(i, j)) return best递归函数里的四个方向我习惯按“下、上、右、左”的顺序写其实顺序不影响结果。注意一点标记visited[i][j] True必须放在递归调用之前。如果放在递归之后或者放在最后一个方向处理完之后同一个格子会在多个分支里被重复进入轻则重复计数重则无限递归。3.4 更简洁的淹没法版本如果你确定可以修改输入淹没法的代码会短很多from typing import List class Solution: def maxAreaOfIsland(self, grid: List[List[int]]) - int: m, n len(grid), len(grid[0]) def dfs(i: int, j: int) - int: if i 0 or i m or j 0 or j n or grid[i][j] 0: return 0 grid[i][j] 0 return 1 dfs(i 1, j) dfs(i - 1, j) dfs(i, j 1) dfs(i, j - 1) best 0 for i in range(m): for j in range(n): if grid[i][j] 1: best max(best, dfs(i, j)) return best淹没法的核心是一旦访问过某个陆地格子立刻把它改成 0。这样之后无论是主循环还是递归里再遇到它都会把它当成水。省掉了 visited 数组空间更省代码也更短。但这里有个工程上的小细节要注意如果面试官问你能不能修改原数组你应该先反问一句“这个输入后面还要用吗”。如果对方说数据不可变你就老老实实写 visited 版本。这个沟通动作本身就能体现你的工程意识。3.5 BFS 版本与栈式 DFS如果你想避开递归深度问题BFS 是更稳妥的选择。核心代码from typing import List from collections import deque class Solution: def maxAreaOfIsland(self, grid: List[List[int]]) - int: m, n len(grid), len(grid[0]) best 0 dirs ((1, 0), (-1, 0), (0, 1), (0, -1)) for i in range(m): for j in range(n): if grid[i][j] ! 1: continue q deque([(i, j)]) grid[i][j] 0 area 0 while q: x, y q.popleft() area 1 for dx, dy in dirs: nx, ny x dx, y dy if 0 nx m and 0 ny n and grid[nx][ny] 1: grid[nx][ny] 0 q.append((nx, ny)) best max(best, area) return best这里有一个 BFS 必须养成的习惯邻居入队之前就标记成 0而不是弹出的时候再标记。如果你等到出队时再标记同一个格子可能被多个邻居重复放进队列队列里会出现同一份地址的多个副本统计面积就会重复。顺带说一句把上面代码里的q.popleft()换成q.pop()队列就变成了栈BFS 就变成了“栈式 DFS”。这是一个验证理解的好练习——你会在实践中感觉到递归本质上是函数调用栈在替你干活换成显式栈之后爆栈风险消失了但搜索顺序从一层层扩散变回了纵深探索。3.6 递归深度的隐性坑695 的题目约束是 m、n 最大 50也就是最多 2500 个格子。如果陆地形状足够刁钻形成一条蛇形通路DFS 的递归深度是可以逼近 2500 的。Python 的默认递归上限一般是 1000超过就会抛 RecursionError。我在本地测试时真踩过这个坑。构造一个 50x50 的蛇形网格陆地像贪吃蛇一样从左上角一路盘绕到右下角不设置递归上限直接报错。加上下面两行就没问题了import sys sys.setrecursionlimit(10000)LeetCode 的评测机上大部分 DFS 提交不写递归上限也能过是因为测试数据没有极端到那个程度。但作为一个有经验的写代码的人我还是建议在脚本开头显式调大递归上限或者直接用 BFS。面试时如果被问到“图太大递归爆了怎么办”这也是一个很好的追问切入点。4. 边界与复杂度这些细节决定你能不能一次过4.1 空输入、全 0、单行单列题目虽然保证了 m、n 至少是 1但真实工程里的代码还是要有防御空数组if not grid or not grid[0]: return 0。全 0主循环永远不会进入 DFS最后返回初始值 0。单行单列比如[[1, 1, 1]]DFS 只会往左右两个方向走正确结果是 3。递归函数里的边界判断已经处理了越界问题不需要额外写逻辑。很多线上测评的隐藏测试会包含这些特殊形状防御逻辑写全一次就能过不用反复提交去猜错在哪。4.2 标记置位的时机决定程序是“对”还是“死循环”前面已经提过这里再强调一次递归版进入 DFS 函数后立刻标记visited[i][j] True或立刻把grid[i][j] 0。BFS 版邻居入队时立刻标记而不是出队时标记。如果标记晚了会出现的现象是格子 A 和格子 B 相邻A 先访问到 B 的时候 B 还没标记B 入队随后 A 又被 B 访问到于是两个格子互相反复触发。对递归版来说就是无限递归对 BFS 版来说就是队列暴增、结果重复。这个细节我见过太多人踩了它甚至比“忘了写 visited 数组”更隐蔽。4.3 复杂度推导与空间优化真相时间复杂度每个格子最多被主循环访问一次进 DFS/BFS 一次。每次访问时检查四个方向每次检查都是常数操作。所以整体是 O(m*n)其中 m 是行数、n 是列数。空间复杂度要分两部分看visited 数组O(m*n)。递归调用栈最坏情况是所有陆地连成一条长蛇递归深度达到 O(m*n)。淹没法虽然省掉了 visited 数组但递归栈仍然是 O(mn)。所以严格来说淹没法的空间复杂度是 O(mn)而不是 O(1)。只有在“忽略递归栈”这个前提下才能说它是 O(1)。面试时你把这一点讲清楚反而会让面试官觉得你理解到位。BFS 的队列空间也是 O(m*n)最坏情况是整张网格全是 1队列里一度装上大量陆地格子。实际操作中因为标记及时每个格子只会进队一次空间总量仍然可控。4.4 LeetCode 实测表现与优化误区我在 LeetCode 上跑过 DFS 淹没版和 BFS 版两者耗时几乎没有可感知的差别因为 m、n 最大值只有 50测试规模很小。真正会让代码变慢的反而是一些无谓的预处理比如有人喜欢先把整张二维数组转成字符串数组或者把每个格子包装成对象这些额外开销在这个量级下完全没必要。另外很多人会纠结“我用不用把方向数组写成两个一维数组是不是比元组列表快”。不要在这种地方做微优化。代码的可读性优先方向数组写成dirs ((1,0), (-1,0), (0,1), (0,-1))就够了。递归版里直接手写四次递归调用也很直观还可以少一层循环。选择你觉得讲起来最容易的那种写法。4.5 面试中怎么展示这道题如果面试遇到这道题我的建议节奏是先用自己构造的小例子口述思路说清楚“我们要找的是网格图里的连通分量”。主动问面试官能修改输入的 grid 吗如果不能我就用 visited 数组。写代码时优先选 visited 版本因为它不破坏输入数据。写完后快速自查三个边界空数组、全 0、单行单列。这套流程不需要额外背什么东西就是把工程习惯搬到白板上。很多候选人代码本身没问题但从不主动检查边界给面试官的观感就差一截。你主动把边界过了整体印象会完全不同。5. 从 695 出发建立你的“岛屿问题模板”5.1 同框架的兄弟题一张表岛屿系列题目很多但核心骨架基本一致。我做了一个简单映射题号题目核心变化点与 695 的关系200岛屿数量只统计有几块岛不统计面积去掉 max改成计数463岛屿周长统计边界长度递归遇水或越界时加 1130被围绕的区域把被水围住的 O 改成 X从边界 O 反向搜索827最大人工岛允许把一个 0 改成 1先给岛编号再枚举 01254统计封闭岛屿边界上的岛不算封闭岛类似 130 的边界排除法1020飞地的数量统计无法到达边界的陆地数边界排除后数剩余 1这张表可以当作刷题地图。你每做一道就回到 695 的模板上标一下“改了什么”这样比孤零零地刷几十道题记忆效果好得多。5.2 逐个拆解差异200 岛屿数量是最直接的兄弟题。695 是取最大面积200 是在 DFS 入口处count 1不关心每个连通块内部有多少个格子。代码量甚至更短。463 岛屿周长稍微绕一点。DFS 时当前格子是陆地如果它朝着某个方向走一步是水或者越界说明这个方向有一条暴露在外的边周长加 1。如果走一步是陆地就继续递归。也有一个公式化的做法周长等于陆地块数乘以 4 减去相邻陆地边数乘以 2。两个思路都可以但前者和 DFS 模板的契合度更高。130 被围绕的区域要求找出被水完全包围的 O把它们改成 X而边界上的 O 例外。所以套路是从边界上的 O 开始做 DFS把所有与边界连通的 O 先标记成一个特殊符号比如 B。最后遍历整个矩阵剩下的 O 就是被包围的改成 X再把 B 改回 O。这里“搜索起点”变了从遍历全图找某个状态变成从边界出发反向标记。827 最大人工岛是 695 的进阶版。思路分两段第一遍遍历给每一座岛编号同时用哈希表记录每个编号对应的面积第二遍枚举每一个 0 位置看它上下左右四个方向命中了哪些岛的编号把命中岛的面积加起来再额外加 1这就是把这个 0 改成 1 之后能得到的面积。注意四个方向可能命中的是同一座岛要去重。这个题的难点已经从“搜索”转移到了“编号和集合统计”。1254 统计封闭岛屿和 1020 飞地的数量核心都是边界排除法先把边界上能走到的岛屿区域处理掉剩下的才是真正符合条件的。处理完之后1254 数还剩下几座岛1020 数还剩下多少块陆地。5.3 抽象成一套通用模板做多了之后你可以把这些题抽象成最简单的模板遍历每个格子: 判断是否可以作为搜索入口 进入 DFS / BFS 搜索 搜索函数内部: 越界判断 状态判断是不是目标是不是已访问 标记已访问 扩展邻居四个方向 在主循环汇总结果695 的面积统计200 的数量统计463 的边界统计130 的边界感染827 的编号连接全部落在这个骨架里。你只要搞清楚两件事搜索入口是什么汇总时统计什么。剩下的递归逻辑完全一致。我自己的习惯是每刷一个新的网格搜索题就先在纸上写出模板然后在模板上标注“这题改的是哪一行”。这个方法帮我节省了大量重复思考时间也让我真正把岛屿系列吃成了体系而不是做一道忘一道。希望这个思路对你也一样有用。最后分享一个我实际踩出来的经验做这类网格搜索题动手前先想清楚两个问题——这个图最多会递归多深同一个格子会不会被重复访问把这两个问题在脑子里过完再写代码一次过的概率会高很多。 
长河君 · 2026/10/9 6:37:28 · 阅读 1.2k LeetCode 695岛屿最大面积：DFS、BFS与并查集全解法详解
我第一次正经刷题碰到“695岛屿最大面积”应该算是比较晚的。当时数组和链表这些基础还没完全过完看到题目里那张 0 和 1 组成的网格第一反应是这不是两层循环暴力数一下就行了吗等真动手写才发现“怎么判断相邻的 1 属于同一块陆地”“已经数过的格子怎么避免重复计数”这些看似基础的问题一旦没想清楚代码写出来就全是坑。这道题本身不难给定一个 m x n 的二维数组1 表示陆地、0 表示水水平或垂直方向相邻的 1 组成一块岛屿要求返回所有岛屿中的最大面积没有岛屿就返回 0。它本质上是一个“网格连通域”问题也是 DFS、BFS 搜索最经典的入门题。这篇文章我会从题目模型、三种解法、代码实现到容易踩的坑以及它背后能延伸出去的一串兄弟题一次性讲透。适合刚开始刷题、对递归和搜索还不熟的读者也适合想把地图类搜索题整理成体系的人。1. 先把题目模型拆明白一个二维数组就是一张图1.1 用一个更小的例子手动跑一遍官方给的是一个好几行的网格初看容易晕。我换成更小的 4 行 4 列自己手动过一遍思路立刻就清楚了。1 0 1 1 1 0 0 1 0 0 0 0 0 1 1 0左上角位置 (0,0) 和 (1,0) 上下相邻组成一块面积是 2。右上角(0,2)、(0,3)、(1,3) 这三个位置通过水平和垂直方向连在一起面积是 3。底部(3,1) 和 (3,2) 左右相邻面积是 2。最大面积就是 3。这个例子看起来简单但它其实纠正了一个常见误解题目里的“面积”并不是我们日常说的矩形面积而是“同一个连通块中的格子总数”。LeetCode 里称为 area英文描述也写得很清楚。有人第一次做这题会下意识在网格上画一个包围盒然后用长乘宽去算结果跟答案完全对不上就是这个概念没转过弯。1.2 相邻的定义是四方向不是八方向题目明确说了水平或垂直相邻才算同一块。也就是说两个格子如果只是在斜对角方向碰了一下不算同一座岛。比如一张网格里 (0,0) 是 1(1,1) 也是 1但 (0,0) 和 (1,1) 之间既没有共同边也没有路径那它们就是两座独立的岛屿。很多初学者在写方向数组的时候会不自觉地把四个方向扩成八个方向多算了左上、右上、左下、右下。这样做的后果很直接原本两座不相连的岛被你强行拼成一座面积直接翻倍。如果你之前接触过图像处理里的连通区域标记可能会遇到 8 连通的概念那是另一套规则。不同的题目有不同的定义刷 LeetCode 的岛屿系列时先确认题目说的是 4 连通还是 8 连通永远是一个好习惯。695 里只用四个方向上、下、左、右。1.3 网格本身就是一种图的存储方式第一次接触图论的人总以为图一定要写成邻接表或者邻接矩阵。其实二维网格本身就是一种图每个格子是一个节点相邻关系就是边1 表示这个节点存在0 表示不存在。找岛屿本质上就是找出这个图里的所有连通分量并统计每个连通分量的规模。想通这一点后面很多题都能统一起来。比如你之后做岛屿数量、岛屿周长、被围绕的区域会发现代码骨架几乎一样差别只在搜索入口和统计方式。这也是为什么我推荐把 695 当作模板题来做它的数据是规则的网格不需要建图坐标本身就是节点省掉了一大截抽象成本。你只需要专注理解 DFS 和 BFS 的核心逻辑而不是纠结“这个图到底怎么存”。2. 动手之前的选择DFS、BFS、并查集能解但气质不同2.1 DFS顺着一条路走到黑再回头DFS 的思想用一句话说从一个陆地格子出发标记它已经被访问过然后向上下左右四个方向继续探索遇到水或越界就停下遇到没访问过的陆地就继续递归。拿生活场景类比你在一片空地上泼一桶水水会顺着每一条通道往前流流到尽头再回溯最后所有被水浸湿的格子就是同一块区域。这个“浸湿”的动作就是标记访问。在 695 里DFS 的返回值可以直接设计成面积当前格子本身算 1再加上四个方向递归返回的面积。代码层面非常优雅不需要额外维护一个计数器。我在下面会给你完整实现这种“1 四个方向的递归结果”的写法比在外面定义一个变量累加要清晰得多也不容易漏重置。2.2 BFS一层一层向外扩散BFS 的思想是使用队列从一个陆地格子出发把它放进队列然后循环弹出队首格子扩展它的四个方向把相邻的陆地格子继续放进队列。队列空了说明这一整块岛屿都访问完了。类比一下更像一个消息从原点向外一层层扩散每一轮扩散把所有“新感染”的格子放进队列尾部。BFS 的好处是迭代实现没有递归调用所以不存在递归深度过大导致爆栈的问题。代价是代码比 DFS 长一点需要显式维护一个队列。2.3 并查集把合并关系变成集合关系第三种思路是并查集看问题的角度完全不同每个 1 格子一开始都是独立的“小岛”面积都是 1。然后遍历网格碰到相邻的 1 就把它们合并成一个集合同时把面积累加到根节点上。最后扫描所有格子找出面积最大的根节点。并查集在静态网格上看起来有点“杀鸡用牛刀”但它的价值在于可以处理动态合并的场景。比如 LeetCode 827 最大人工岛允许你把某个 0 改成 1然后再求最大岛屿面积这类题用并查集的视野会舒服很多。并查集的关键操作就两个find 找根节点union 合并两个集合。如果希望合并后快速知道每个集合的规模就额外维护一个 size 数组合并时把子集的 size 加到父集上。核心代码片段大概是这样的class DSU: def __init__(self, n): self.parent list(range(n)) self.size [1] * n def find(self, x): while self.parent[x] ! x: self.parent[x] self.parent[self.parent[x]] x self.parent[x] return x def union(self, a, b): ra, rb self.find(a), self.find(b) if ra rb: return if self.size[ra] self.size[rb]: ra, rb rb, ra self.parent[rb] ra self.size[ra] self.size[rb]然后在主循环里把二维坐标映射成一维索引i * n j每个 1 格子只和右侧、下侧的邻居合并。这样每条相邻边只会被处理一次不会重复。2.4 三种方案对比与选择方案核心依赖时间复杂度空间复杂度优点注意点DFS递归 / 系统栈O(m*n)O(m*n) 递归栈代码最短语义最贴切递归深度可能超限BFS显式队列O(m*n)O(m*n) 队列空间迭代实现不易爆栈代码略长要小心重复入队并查集父子数组O(mnα)O(m*n)可扩展动态合并场景抽象度更高第一次接触要适应我的建议是第一次做这道题优先掌握 DFS因为代码最直观也最容易讲清楚思路。但心里要对 BFS 和并查集两个版本有概念。面试时如果考官追问“网格特别大、递归爆栈了怎么办”你能立刻切换到 BFS 或者显式栈会非常加分。3. 从思路到代码以 DFS 为主线写一遍标准解3.1 主循环与递归函数的分工整套代码只有两个部分。第一部分是主循环遍历整个网格如果当前格子是 1 且没有被访问过就把它当作一座岛屿的起点调用递归函数把这个连通块全部扫一遍。每个新扫出来的面积都去更新全局最大值。第二部分是递归函数给定一个坐标 (i, j)先判断越界、是否是陆地、是否已经访问过。如果条件都不满足就标记已访问然后递归处理四个方向。返回值是当前格子 1 加上四个方向的递归结果。这个分工模式几乎是所有网格搜索题的万能骨架。后面做岛屿数量、岛屿周长改的都是这两部分里的统计逻辑整体结构不会变。3.2 两个关键实现细节标记与返回值第一个坑是标记已访问。最常用的两种方式维护一个独立的 visited 二维数组初始全是 False访问过就置为 True。直接修改原数组把已经访问过的 1 改成 0这种技巧常叫“淹没法”或“沉岛法”。如果面试或者在真实工程项目里我更推荐 visited 数组原因很简单它不破坏原始输入。有些场景里 grid 后续还要复用你直接改成 0 之后数据就丢了。但 LeetCode 刷题无所谓很多人喜欢淹没法因为代码更短。两种都要会我下面都会给你。第二个细节是统计面积的方式。用返回值比用全局变量舒服很多。如果你在外面定义一个area在递归里area 1那每次从新起点开始之前都必须记得把area重置成 0。一旦忘了重置结果会累加上一轮的数据。用返回值的话每个递归子问题各自返回自己的面积逻辑天然闭合不容易出错。3.3 Python 标准实现visited 版本from typing import List class Solution: def maxAreaOfIsland(self, grid: List[List[int]]) - int: if not grid or not grid[0]: return 0 m, n len(grid), len(grid[0]) visited [[False] * n for _ in range(m)] best 0 def dfs(i: int, j: int) - int: if i 0 or i m or j 0 or j n: return 0 if grid[i][j] 0 or visited[i][j]: return 0 visited[i][j] True return ( 1 dfs(i 1, j) dfs(i - 1, j) dfs(i, j 1) dfs(i, j - 1) ) for i in range(m): for j in range(n): if grid[i][j] 1 and not visited[i][j]: best max(best, dfs(i, j)) return best递归函数里的四个方向我习惯按“下、上、右、左”的顺序写其实顺序不影响结果。注意一点标记visited[i][j] True必须放在递归调用之前。如果放在递归之后或者放在最后一个方向处理完之后同一个格子会在多个分支里被重复进入轻则重复计数重则无限递归。3.4 更简洁的淹没法版本如果你确定可以修改输入淹没法的代码会短很多from typing import List class Solution: def maxAreaOfIsland(self, grid: List[List[int]]) - int: m, n len(grid), len(grid[0]) def dfs(i: int, j: int) - int: if i 0 or i m or j 0 or j n or grid[i][j] 0: return 0 grid[i][j] 0 return 1 dfs(i 1, j) dfs(i - 1, j) dfs(i, j 1) dfs(i, j - 1) best 0 for i in range(m): for j in range(n): if grid[i][j] 1: best max(best, dfs(i, j)) return best淹没法的核心是一旦访问过某个陆地格子立刻把它改成 0。这样之后无论是主循环还是递归里再遇到它都会把它当成水。省掉了 visited 数组空间更省代码也更短。但这里有个工程上的小细节要注意如果面试官问你能不能修改原数组你应该先反问一句“这个输入后面还要用吗”。如果对方说数据不可变你就老老实实写 visited 版本。这个沟通动作本身就能体现你的工程意识。3.5 BFS 版本与栈式 DFS如果你想避开递归深度问题BFS 是更稳妥的选择。核心代码from typing import List from collections import deque class Solution: def maxAreaOfIsland(self, grid: List[List[int]]) - int: m, n len(grid), len(grid[0]) best 0 dirs ((1, 0), (-1, 0), (0, 1), (0, -1)) for i in range(m): for j in range(n): if grid[i][j] ! 1: continue q deque([(i, j)]) grid[i][j] 0 area 0 while q: x, y q.popleft() area 1 for dx, dy in dirs: nx, ny x dx, y dy if 0 nx m and 0 ny n and grid[nx][ny] 1: grid[nx][ny] 0 q.append((nx, ny)) best max(best, area) return best这里有一个 BFS 必须养成的习惯邻居入队之前就标记成 0而不是弹出的时候再标记。如果你等到出队时再标记同一个格子可能被多个邻居重复放进队列队列里会出现同一份地址的多个副本统计面积就会重复。顺带说一句把上面代码里的q.popleft()换成q.pop()队列就变成了栈BFS 就变成了“栈式 DFS”。这是一个验证理解的好练习——你会在实践中感觉到递归本质上是函数调用栈在替你干活换成显式栈之后爆栈风险消失了但搜索顺序从一层层扩散变回了纵深探索。3.6 递归深度的隐性坑695 的题目约束是 m、n 最大 50也就是最多 2500 个格子。如果陆地形状足够刁钻形成一条蛇形通路DFS 的递归深度是可以逼近 2500 的。Python 的默认递归上限一般是 1000超过就会抛 RecursionError。我在本地测试时真踩过这个坑。构造一个 50x50 的蛇形网格陆地像贪吃蛇一样从左上角一路盘绕到右下角不设置递归上限直接报错。加上下面两行就没问题了import sys sys.setrecursionlimit(10000)LeetCode 的评测机上大部分 DFS 提交不写递归上限也能过是因为测试数据没有极端到那个程度。但作为一个有经验的写代码的人我还是建议在脚本开头显式调大递归上限或者直接用 BFS。面试时如果被问到“图太大递归爆了怎么办”这也是一个很好的追问切入点。4. 边界与复杂度这些细节决定你能不能一次过4.1 空输入、全 0、单行单列题目虽然保证了 m、n 至少是 1但真实工程里的代码还是要有防御空数组if not grid or not grid[0]: return 0。全 0主循环永远不会进入 DFS最后返回初始值 0。单行单列比如[[1, 1, 1]]DFS 只会往左右两个方向走正确结果是 3。递归函数里的边界判断已经处理了越界问题不需要额外写逻辑。很多线上测评的隐藏测试会包含这些特殊形状防御逻辑写全一次就能过不用反复提交去猜错在哪。4.2 标记置位的时机决定程序是“对”还是“死循环”前面已经提过这里再强调一次递归版进入 DFS 函数后立刻标记visited[i][j] True或立刻把grid[i][j] 0。BFS 版邻居入队时立刻标记而不是出队时标记。如果标记晚了会出现的现象是格子 A 和格子 B 相邻A 先访问到 B 的时候 B 还没标记B 入队随后 A 又被 B 访问到于是两个格子互相反复触发。对递归版来说就是无限递归对 BFS 版来说就是队列暴增、结果重复。这个细节我见过太多人踩了它甚至比“忘了写 visited 数组”更隐蔽。4.3 复杂度推导与空间优化真相时间复杂度每个格子最多被主循环访问一次进 DFS/BFS 一次。每次访问时检查四个方向每次检查都是常数操作。所以整体是 O(m*n)其中 m 是行数、n 是列数。空间复杂度要分两部分看visited 数组O(m*n)。递归调用栈最坏情况是所有陆地连成一条长蛇递归深度达到 O(m*n)。淹没法虽然省掉了 visited 数组但递归栈仍然是 O(mn)。所以严格来说淹没法的空间复杂度是 O(mn)而不是 O(1)。只有在“忽略递归栈”这个前提下才能说它是 O(1)。面试时你把这一点讲清楚反而会让面试官觉得你理解到位。BFS 的队列空间也是 O(m*n)最坏情况是整张网格全是 1队列里一度装上大量陆地格子。实际操作中因为标记及时每个格子只会进队一次空间总量仍然可控。4.4 LeetCode 实测表现与优化误区我在 LeetCode 上跑过 DFS 淹没版和 BFS 版两者耗时几乎没有可感知的差别因为 m、n 最大值只有 50测试规模很小。真正会让代码变慢的反而是一些无谓的预处理比如有人喜欢先把整张二维数组转成字符串数组或者把每个格子包装成对象这些额外开销在这个量级下完全没必要。另外很多人会纠结“我用不用把方向数组写成两个一维数组是不是比元组列表快”。不要在这种地方做微优化。代码的可读性优先方向数组写成dirs ((1,0), (-1,0), (0,1), (0,-1))就够了。递归版里直接手写四次递归调用也很直观还可以少一层循环。选择你觉得讲起来最容易的那种写法。4.5 面试中怎么展示这道题如果面试遇到这道题我的建议节奏是先用自己构造的小例子口述思路说清楚“我们要找的是网格图里的连通分量”。主动问面试官能修改输入的 grid 吗如果不能我就用 visited 数组。写代码时优先选 visited 版本因为它不破坏输入数据。写完后快速自查三个边界空数组、全 0、单行单列。这套流程不需要额外背什么东西就是把工程习惯搬到白板上。很多候选人代码本身没问题但从不主动检查边界给面试官的观感就差一截。你主动把边界过了整体印象会完全不同。5. 从 695 出发建立你的“岛屿问题模板”5.1 同框架的兄弟题一张表岛屿系列题目很多但核心骨架基本一致。我做了一个简单映射题号题目核心变化点与 695 的关系200岛屿数量只统计有几块岛不统计面积去掉 max改成计数463岛屿周长统计边界长度递归遇水或越界时加 1130被围绕的区域把被水围住的 O 改成 X从边界 O 反向搜索827最大人工岛允许把一个 0 改成 1先给岛编号再枚举 01254统计封闭岛屿边界上的岛不算封闭岛类似 130 的边界排除法1020飞地的数量统计无法到达边界的陆地数边界排除后数剩余 1这张表可以当作刷题地图。你每做一道就回到 695 的模板上标一下“改了什么”这样比孤零零地刷几十道题记忆效果好得多。5.2 逐个拆解差异200 岛屿数量是最直接的兄弟题。695 是取最大面积200 是在 DFS 入口处count 1不关心每个连通块内部有多少个格子。代码量甚至更短。463 岛屿周长稍微绕一点。DFS 时当前格子是陆地如果它朝着某个方向走一步是水或者越界说明这个方向有一条暴露在外的边周长加 1。如果走一步是陆地就继续递归。也有一个公式化的做法周长等于陆地块数乘以 4 减去相邻陆地边数乘以 2。两个思路都可以但前者和 DFS 模板的契合度更高。130 被围绕的区域要求找出被水完全包围的 O把它们改成 X而边界上的 O 例外。所以套路是从边界上的 O 开始做 DFS把所有与边界连通的 O 先标记成一个特殊符号比如 B。最后遍历整个矩阵剩下的 O 就是被包围的改成 X再把 B 改回 O。这里“搜索起点”变了从遍历全图找某个状态变成从边界出发反向标记。827 最大人工岛是 695 的进阶版。思路分两段第一遍遍历给每一座岛编号同时用哈希表记录每个编号对应的面积第二遍枚举每一个 0 位置看它上下左右四个方向命中了哪些岛的编号把命中岛的面积加起来再额外加 1这就是把这个 0 改成 1 之后能得到的面积。注意四个方向可能命中的是同一座岛要去重。这个题的难点已经从“搜索”转移到了“编号和集合统计”。1254 统计封闭岛屿和 1020 飞地的数量核心都是边界排除法先把边界上能走到的岛屿区域处理掉剩下的才是真正符合条件的。处理完之后1254 数还剩下几座岛1020 数还剩下多少块陆地。5.3 抽象成一套通用模板做多了之后你可以把这些题抽象成最简单的模板遍历每个格子: 判断是否可以作为搜索入口 进入 DFS / BFS 搜索 搜索函数内部: 越界判断 状态判断是不是目标是不是已访问 标记已访问 扩展邻居四个方向 在主循环汇总结果695 的面积统计200 的数量统计463 的边界统计130 的边界感染827 的编号连接全部落在这个骨架里。你只要搞清楚两件事搜索入口是什么汇总时统计什么。剩下的递归逻辑完全一致。我自己的习惯是每刷一个新的网格搜索题就先在纸上写出模板然后在模板上标注“这题改的是哪一行”。这个方法帮我节省了大量重复思考时间也让我真正把岛屿系列吃成了体系而不是做一道忘一道。希望这个思路对你也一样有用。最后分享一个我实际踩出来的经验做这类网格搜索题动手前先想清楚两个问题——这个图最多会递归多深同一个格子会不会被重复访问把这两个问题在脑子里过完再写代码一次过的概率会高很多。