LeetCode 695 岛屿的最大面积算是岛屿系列里最基础的题目了。我刷题那会儿很多题单都把这道题放在DFS/BFS热身的位置但它绝不是那种看一眼就会、随便写写就能过的题目。恰恰是这种基础题最能看出一个人对二维网格搜索的理解是否扎实边界处理、访问标记、递归深度、队列写法随便一个细节都能翻车。这篇文章就从这三条主流路线展开把DFS、BFS、并查集各自的实现逻辑和适用场景拆开讲清楚也会把我在实际做题过程中踩过的坑和调试习惯一并分享出来。无论你是刚开始刷算法题的初学者还是准备面试想快速复习搜索框架的开发者这篇文章应该都能给你一些参考。核心无非四个字遍历、标记、计数——但要把它们做到位并不是背个模板就能解决的事。1. 题目拆解陆地连通块与最大面积1.1 题意里容易踩的坑题目给的输入是一个 m 行 n 列的二维网格 grid每个格子要么是字符 1 表示陆地要么是字符 0 表示海水。岛屿的定义是由上下左右四个方向相邻的 1 组成的一块连通区域。要求返回网格中面积最大的岛屿包含的陆地数量也就是相邻 1 的个数。如果网格里没有岛屿返回 0。这里最容易踩的坑有两个。第一字符 1 是字符串不是整数 1。很多人用 Python 写判断时直接写if grid[i][j] 1结果样例都过不了半天想不通问题出在哪。第二只有上下左右四方向才算相邻斜对角不算。因为网格的离散特性“相邻”这个概念在题目里被刻意限制为四邻域这在图像处理里也叫 4-connectivity而不是 8-connectivity。一开始想不明白的话画一个三乘三的地图把中心设为陆地四个角那几块能不能连成岛屿一下就明白了。1.2 本质是求最大连通分量从图论的角度看grid 里的每个 1 都是一个节点上下左右相邻的 1 之间有一条隐式的无向边。那么一个岛屿就是这副隐式图里的一个连通分量题目求的其实就是所有连通分量里包含节点数量最大的那个。这个视角非常重要因为一旦把问题抽象成图后面所有解法就都清晰了遍历整张图每遇到一个没访问过的节点就用搜索算法把整个连通块扫一遍统计节点数扫完所有连通块后取最大值。我自己喜欢用“像素画填色”来类比这个过程网格就是一张像素画布海水是空白的陆地是涂了色的像素块。你要做的是找出所有连在一起的色块中最大的一块并且统计它到底占了多少个像素。只要把走过的像素改成海水色就能做到不重不漏。这个思路打通之后后面的DFS和BFS都只是在“怎么填色”这件事上选择了不同的顺序而已。1.3 三种主流解法怎么选解决这道题常见的方案有三种DFS、BFS、并查集。三者的核心目标一致都是遍历所有陆地格子并统计连通块面积差别在于遍历的组织方式。解法核心思想时间复杂度空间复杂度最适用的场景DFS递归向四个方向深入直到越界或遇水O(R×C)O(R×C) 递归栈代码简洁面试最常写BFS用队列逐层扩散类似水波蔓延O(R×C)O(R×C) 队列避免递归爆栈适合超大网格并查集用不相交集合并相邻陆地统计每块大小O(R×C×α)O(R×C)题目升级为动态添加陆地时从实际刷题的角度来说我建议至少把DFS和BFS两种写法都练熟。DFS写起来顺手BFS在极端数据下更安全。并查集虽然这道题用起来有点“杀鸡用牛刀”但如果后续想挑战带动态变化的岛屿问题那这个思路反而是最值得提前铺垫的。2. DFS实现最直观也最常用2.1 递归函数的三步设计DFS解法里的递归函数设计思路可以拆成三步先判边界再判当前格是否有效最后扩展。第一步处理越界。递归到网格边缘之外直接返回0。第二步看当前格子是不是陆地。如果已经是海水说明这个格子要么本来就不是陆地要么已经被访问过并标记掉了也返回0。第三步如果确定是陆地立刻把当前格子标记为海水也就是赋值成 0然后继续向上下左右四个方向递归。这里有一个特别容易忽略的细节标记动作务必放在递归之前。只要你进入了一个陆地格子它就已经被“占用”了不能再被其他方向的递归重复访问。如果你先把递归写进去再回头标记就会形成死循环两个格子互相反复调用直到栈爆炸。四方向的扩展我习惯写成四个显式的递归调用不额外写方向数组。这样代码长一点但每一步都清晰可见对于初学者来说反而更容易理解。核心逻辑就是def dfs(r, c): # 越界返回 0 if r 0 or r R or c 0 or c C: return 0 # 不是陆地返回 0 if grid[r][c] ! 1: return 0 # 标记为海水表示已访问 grid[r][c] 0 # 当前格子算 1 个面积再加上四个方向的面积 return 1 dfs(r 1, c) dfs(r - 1, c) dfs(r, c 1) dfs(r, c - 1)2.2 完整代码与复杂度主函数里用双重循环扫描整个网格。每次遇到一个岛屿的第一个陆地格子就调用dfs得到整个连通块面积再用 ans 记录最大值。整体代码非常紧凑。from typing import List class Solution: def maxAreaOfIsland(self, grid: List[List[str]]) - int: R, C len(grid), len(grid[0]) ans 0 def dfs(r: int, c: int) - int: if r 0 or r R or c 0 or c C: return 0 if grid[r][c] ! 1: return 0 grid[r][c] 0 return 1 dfs(r 1, c) dfs(r - 1, c) dfs(r, c 1) dfs(r, c - 1) for r in range(R): for c in range(C): if grid[r][c] 1: ans max(ans, dfs(r, c)) return ans时间复杂度是 O(R×C)因为每个格子最多被访问一次要么被主循环访问要么被递归访问时直接标记成了海水后续不会再进来。空间复杂度最坏也是 O(R×C)这是由递归栈深度决定的。如果整个网格全是陆地递归会从左上角一路探到右下角栈深度接近R×C。这也是DFS最让人不放心的地方小数据没问题大数据量随时可能爆栈。2.3 递归深度这件事Python 默认的递归深度上限是 1000 左右。LeetCode 上这道题虽然通常不会给到极端全陆地的超大网格但你不能保证每日一题或者编辑器里的隐藏测试不会加一个 1000×1000 的全 1 地图。一旦触底就会抛出 RecursionError也叫最大递归深度超限。解决方式有两种。最省事的办法是在文件头部加上递归上限import sys sys.setrecursionlimit(1000000)但这只是提高了 Python 层的递归上限底层的C栈依然有物理限制。如果真给了一个极大的全陆地地图即使设置了递归上限程序也可能因为C栈溢出而直接崩溃这种崩溃通常不是异常而是进程死亡调试起来非常痛苦。所以在我的经验里一旦题目数据范围可能超过 500×500而且岛屿图形状特别“长条”用DFS就要多留个心眼。真想稳妥就用BFS或者显式栈来写。3. BFS实现用队列稳住大图3.1 队列实现的核心逻辑BFS解法的思路是把当前陆地格子塞进队列然后一层一层往外扩散。每个格子出队时面积加1同时把它上下左右的陆地邻居入队并立刻标记成海水。直到队列为空说明这个连通块扫完了。关键点在于入队的同时就要标记。也就是说一个格子只要被加入队列它的状态就是“已访问”再也不能被其他格子重复入队。如果你等到出队时才标记那两个邻居可能同时把同一个格子加进队列两次面积统计就会出错而且死循环的风险也很大。以下是完整的代码实现from collections import deque from typing import List class Solution: def maxAreaOfIsland(self, grid: List[List[str]]) - int: R, C len(grid), len(grid[0]) ans 0 directions [(1, 0), (-1, 0), (0, 1), (0, -1)] for i in range(R): for j in range(C): if grid[i][j] ! 1: continue q deque() q.append((i, j)) grid[i][j] 0 cur 0 while q: x, y q.popleft() cur 1 for dx, dy in directions: nx, ny x dx, y dy if 0 nx R and 0 ny C and grid[nx][ny] 1: grid[nx][ny] 0 q.append((nx, ny)) ans max(ans, cur) return ansBFS整体代码量比DFS略大一点但逻辑上没有递归结构非常清晰外层扫描起点内层队列扩散。这种写法在任意规模的网格下都不会有栈溢出问题稳定性远高于递归DFS。3.2 为什么用deque而不是list这里必须多说一句Python的list也可以当队列用比如q.pop(0)能取出队首元素但它的时间复杂度是 O(n)。因为list是连续存储结构从头部弹出元素会导致所有剩余元素前移一位。如果网格比较大这个操作会迅速拖垮性能甚至让你超时。collections.deque是双端队列底层用双向链表实现popleft()是 O(1)两个方向的插入和弹出都很高效。BFS场景下这是最自然的数据结构选择不要为了少一行import而用list硬撑。3.3 DFS与BFS怎么选择从这道题的角度DFS和BFS最终返回的结果完全一样区别只体现在遍历顺序和资源占用上。对比维度DFSBFS代码风格递归短小精悍抽象层次高循环迭代结构直白空间风险递归栈可能爆栈队列在堆上分配更稳定遍历顺序一条路走到底再回头层层扩散调试难度递归调用链不好跟踪队列状态直观可逐步打印如果你问我实际做题怎么选我的习惯是默认先写DFS因为最快如果题目数据范围比较大或者用了Python担心递归上限就切到BFS。另外还有一个折中方案显式栈模拟DFS。思路和BFS几乎一样只是把deque换成普通list把取出队首改成弹出栈顶也就是用stack.pop()然后依然维持“入栈时立即标记”的规则。这样既能保留DFS的深度优先语义又不需要递归。多数情况下对于只求面积这道题DFS和BFS谁先谁后无所谓。但如果面试官追问遍历顺序对结果有没有影响你要能说清楚对连通块面积统计来说没影响但对“路径类”问题会有微妙区别。4. 并查集解法换个角度数面积4.1 并查集建模与二维坐标映射并查集英文叫Union-Find核心支持两个操作把两个节点合并到同一集合以及查询某个节点所在集合的代表节点。这道题要统计每个连通块的大小本质上就是维护“同一岛屿”的节点集合。要把二维网格映射成一维下标常用的方式是id r * C c也就是按行优先顺序给每个格子分配唯一编号。这样一来并查集的parent数组和size数组只需要一维长度 R×C 就够用了。初始化时所有陆地节点的parent指向自己size为1海水节点的size可以是0。接着遍历网格对每个陆地节点只向右和向下两个方向检查邻居是否也是陆地。是就把两个节点合并。这里只检查两个方向就够了因为合并是无向的当前格子与左边的邻居在遍历到左边邻居时已经向右边合并过与上边邻居同理。4.2 完整实现与合并方向说明union时还要注意按size合并也就是把size较小的集合挂到size较大的集合下面这样能尽量控制树的深度让find操作更快。from typing import List class DSU: def __init__(self, n: int): self.parent list(range(n)) self.size [0] * n def find(self, x: int) - int: while self.parent[x] ! x: # 路径压缩 self.parent[x] self.parent[self.parent[x]] x self.parent[x] return x def union(self, a: int, b: int) - None: 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] class Solution: def maxAreaOfIsland(self, grid: List[List[str]]) - int: R, C len(grid), len(grid[0]) dsu DSU(R * C) def idx(r: int, c: int) - int: return r * C c for r in range(R): for c in range(C): if grid[r][c] 1: dsu.size[idx(r, c)] 1 if r 1 R and grid[r 1][c] 1: dsu.union(idx(r, c), idx(r 1, c)) if c 1 C and grid[r][c 1] 1: dsu.union(idx(r, c), idx(r, c 1)) ans 0 for r in range(R): for c in range(C): if grid[r][c] 1: root dsu.find(idx(r, c)) ans max(ans, dsu.size[root]) return ans最后再遍历一次所有陆地节点找到它们根节点对应的size最大值。由于union时已经按大小合并根节点的size就是该连通块的节点总数所以直接取最大值即可。时间上并查集在路径压缩和按size合并的共同作用下单次操作接近O(1)整体接近O(R×C)。空间上需要一个长度R×C的parent数组和size数组也在O(R×C)级别。4.3 什么情况才推荐用并查集这道题用并查集确实有点“大材小用”。DFS和BFS写起来更直接思维负担也小。但有一个场景非常值得提前练习题目升级成动态添加陆地并且每次添加后都要询问当前最大岛屿面积。这时DFS和BFS每次都需要全图重扫一遍代价很高并查集却可以在线维护合并结果复杂度优势非常明显。刷题不能只看一道题能不能过还要看解法能否迁移。这道题如果你能把并查集版本也写熟以后再遇到“动态连通性”相关的题目就会轻松很多。5. 易错点与调试心得5.1 提交不过的常见原因我把实际刷题中比较常见的错误整理成了表格方便对照自查。现象可能原因解决方式小样例通过大样例超时没有在入队/递归时立刻标记导致同一个格子被反复访问入队或递归前就置为海水所有输出都是0判断时写成了整数1而不是字符1类型检查grid[i][j] ! 1递归报错RecursionErrorDFS递归深度超过Python默认上限设置递归上限或改用BFS/显式栈对角线误判成相邻理解成了8-connectivity只用四方向数组统计面积偏大标记时机过晚导致重复计数标记动作要在递归或入队之前如果你卡在一个用例上很久优先检查的永远是最基础的几件事输入类型、边界条件、标记位置。很多时候不是算法思路错了只是细节没对齐。5.2 本地验证用例集写完代码后别急着提交。我习惯先在本地跑一组手写的测试用例覆盖不同形态的地图。这里分享几个我觉得必测的场景全是海水[[0,0],[0,0]]期望返回0。全是陆地[[1,1],[1,1]]期望返回4。单个陆地格子[[1]]期望返回1。多个岛屿并排形状不规则例如一个2×2方块和一个长条。细长蛇形岛屿容易触发递归深度。测试用例不是越多越好关键是每种边界情况都要覆盖到。全0和全1是验证主函数流程是否正常的最简单手段蛇形岛屿则是验证搜索算法会不会因为递归过深而崩溃的利器。5.3 三个省时间的调试技巧第一个技巧打印grid观察访问路径。DFS或者BFS过程中把当前访问到的坐标打出来同时打印更新后的grid你会很直观地看到搜索是怎么扩散的。特别是发现某些格子被重复访问时一眼就能看出标记位置写错了。第二个技巧小地图上手动演算。我指的是用一个很小的网格比如3×3自己数清楚岛上每个格子的上下左右邻居然后对比程序结果。这比在大数据集上猜问题高效得多尤其适合排查“为什么面积多出来一块”这种问题。第三个技巧善用断言。在主循环里临时加一行assert grid[i][j] in (0, 1)能帮你提前发现输入类型问题。尤其是当题目给的输入格式和你预期不一致时这种防御性写法能省下不少排查时间。6. 从695到岛屿系列全家桶6.1 岛屿问题变体速查这道题是岛屿系列的敲门砖。掌握了DFS/BFS标记连通块的套路之后很多变体其实都是在这个框架基础上做加减法。变体改动点一句话思路岛屿数量统计连通块个数每遇到陆地就DFS/BFS并计数岛屿周长统计岛屿边界长度越界或遇水时周长加1最大岛屿面积统计最大连通块大小每次搜索完更新ans封闭岛屿数量边缘岛屿不计入先标记所有边缘可达区域被包围的区域将不被包围的O保留从边缘O开始搜索并标记我的经验是把这些变体放在一起刷效果远比单题逐个刷要好。因为它们共享同一套搜索框架你只需要调整统计方式和边界判断就能快速迁移。学一个框架解决一串题这个性价比很高。6.2 搜索框架的价值与延伸除了岛屿系列这种“网格搜索已访问标记”的模型还能延伸到很多场景。比如迷宫寻路、地图分析、游戏里的连通区域检测甚至图像处理中的连通域标注核心逻辑都是相同的。你掌握了在网格上安全地做DFS或BFS的方法就等于掌握了二维空间搜索的基本功。再往深处走一步如果把多个起点同时放入BFS队列就成了多源BFS可以用来求解“每个点到最近陆地的最短距离”这类问题。695这道题虽然起点每次只有一个但从单源扩展到多源只是一个很小的思维跳跃。所以我一直觉得这种看起来简单的“基础题”恰恰是最值得反复打磨的。你把DFS、BFS、并查集三条路都写一遍再把标记逻辑、边界逻辑、复杂度分析都讲清楚面试时遇到任何网格搜索问题心里都会非常有底。刷这道题最深的体会是解法看似简单但每一版实现里都藏着值得推敲的细节。我建议你不要只满足于“提交通过”而是动手把DFS写一遍再把BFS写一遍时间允许的话试试并查集。每次换一种实现方式你对“遍历-标记-计数”这三个动作的理解就会更深一层。最后再分享一个小技巧刷题时把本地调试的print打开真正去看一次扫描路径。你会亲眼看到DFS如何一路扎到边界再折返也会看到BFS如何均匀地从中心向外扩散。这种直观印象比背十遍模板都管用。