拓冰网站定制 
1. 题目拆解它到底在考什么1.1 题面速览与核心诉求力扣695题题目全称“岛屿的最大面积”是“岛屿问题”系列里非常经典的一道入门题。题面很简短给你一个二维网格 grid每个格子要么是 0代表水要么是 1代表陆地。水平或垂直方向上相邻的 1 连在一起构成一座岛屿。要求返回网格中面积最大的岛屿即最大的连续 1 的数量。这个题我第一次见到时第一反应是“这不就是数格子吗”确实它本质上就是数格子但难点在于如何把“连在一起的格子”正确地归为一组并且不重不漏地统计出每一组的数量。很多人一上来就直接双重循环遍历数组看到 1 就 count结果统计出来的根本不是岛屿面积而是全图一共有多少个陆地块。这就是没有理解“连通区域”这个核心概念。这道题的定位很精准它考察的是图的遍历具体来说是寻找无向图连通分量的最大大小。二维网格本身就是一张隐式的图每个格子是一个节点上下左右相邻的格子之间有一条边。你要做的就是找出所有连通分量记录它们的大小返回最大值。1.2 为什么说它是“连通分量”问题从数据结构的角度看grid 可以看作是图的一种邻接矩阵式表示。每个格子相当于一个节点四邻域上、下、左、右连接关系就是边。题目不允许斜对角相邻这非常重要很多初次接触的人容易把斜方向的格子也当成同一座岛屿然后面积就多算了。把问题抽象成连通分量后解法套路就清晰了遍历每一个格子当遇到一个未被访问过的 1 时从它出发把与之相连的所有 1 都找出来这个集合就是一个连通分量也就是一座岛屿。记录这个集合的大小继续遍历后面的格子直到整个网格扫描完成。这里有个关键点你需要注意一座岛屿只能被统计一次。如果每遇到一个 1 就去数一遍跟它相连的所有 1那么同一座岛屿里的每个 1 都会被当一次起点面积会重复计算多次结果会离谱到无法直视。解决办法是“标记已访问”这是所有岛屿类题目通用的解题框架。1.3 这类题的标准解题框架记一下这个模板它处理的不只是695题后面刷 200岛屿数量、130被围绕的区域、1254统计封闭岛屿的数目、827最大人工岛都能复用第一层循环遍历网格的每一个格子判断条件当前格子是陆地grid[i][j] 1并且没有被访问过扩展动作从当前格子出发向上下左右四个方向递归或队列扩展把相邻的陆地全部标记为已访问并统计数量更新答案每次找出一个岛屿后用它的面积更新最大面积。这套框架里面遍历方式可以选深度优先搜索DFS或广度优先搜索BFS标记方式可以选额外的 visited 数组也可以直接改原数组。不同的选择对应不同的写法和复杂度特点接下来我会逐个拆开讲。2. DFS递归版最直接的通解2.1 前置约定如何不走回头路DFS 的写法最贴合人脑的直觉站在一个陆地块上先把这个块算进当前岛屿的面积然后从它出发依次查看上下左右四个方向如果邻居也是陆地就继续走过去再重复“数自己、看邻居”的动作直到周围全是水或者边界才停下。这里最大的隐患是“回头路”。假设 A 的右边是 BB 的左边就是 A。你从 A 走到 B 之后如果不做任何标记B 检查左边邻居时又会走回 A然后再去右边、上边、下边两边互相反复横跳最终导致栈溢出。所以必须保证每个格子最多被“作为当前节点”处理一次。最简单的方式就是“沉岛”一旦访问过一个陆地格子立刻把它改成 0相当于让它沉到水下去后面这个格子就不再被当作陆地了。这个技巧很暴力但极其有效而且不需要额外的空间后面第4章我会专门分析。2.2 递归函数的四个出口写递归的 DFS 时函数开头一定是判断“当前格子能不能走”这是递归四要素里的终止条件。典型的判断顺序是行下标越界i 0 || i grid.length就返回 0列下标越界j 0 || j grid[0].length就返回 0当前格子是 0水就返回 0当前格子已经处理过如果用了 visited 数组会判断 visited[i][j]就返回 0。前两个是边界防护第三个是海洋防护第四个是防回头路防护。四个条件都过了这个格子才是真正可以走、需要数的陆地。只要有一个条件触发直接返回 0不再往下扩展。2.3 完整代码与逐行注释以 Java 写法为例这一版也是我刷题时最常写的class Solution { public int maxAreaOfIsland(int[][] grid) { int maxArea 0; for (int i 0; i grid.length; i) { for (int j 0; j grid[0].length; j) { // 每个格子都可能成为一座岛的起点 if (grid[i][j] 1) { // 从这个起点出发数出整座岛的面积 maxArea Math.max(maxArea, dfs(grid, i, j)); } } } return maxArea; } private int dfs(int[][] grid, int i, int j) { // 出口判断越界 or 水 or 已沉没 if (i 0 || i grid.length || j 0 || j grid[0].length || grid[i][j] 0) { return 0; } // 沉岛避免回头路同时让这个格子不再被统计 grid[i][j] 0; // 当前这一格算 1再加上四个方向的递归结果 return 1 dfs(grid, i - 1, j) dfs(grid, i 1, j) dfs(grid, i, j - 1) dfs(grid, i, j 1); } }这段代码里return 1 dfs(上) dfs(下) dfs(左) dfs(右)是整个 DFS 的核心表达式。它把当前格子的面积 1 和四个方向探索到的所有陆地面积累加在一起。每次递归调用返回的是“以这个格子为起点能到达的一片陆地”的大小。用 Python 写也差不多class Solution: def maxAreaOfIsland(self, grid: List[List[int]]) - int: max_area 0 rows, cols len(grid), len(grid[0]) for i in range(rows): for j in range(cols): if grid[i][j] 1: max_area max(max_area, self.dfs(grid, i, j)) return max_area def dfs(self, grid, i, j): if i 0 or i len(grid) or j 0 or j len(grid[0]) or grid[i][j] 0: return 0 grid[i][j] 0 return 1 self.dfs(grid, i - 1, j) self.dfs(grid, i 1, j) \ self.dfs(grid, i, j - 1) self.dfs(grid, i, j - 1) # 注意这里等等Python 版里的 j 1 方向如果手误写成了 j - 1左右方向就会被重复计算左边会被数两遍右边不会去导致面积偏大。这是复制粘贴类错误里非常典型的一种写完后务必检查四个方向的坐标变化。正确写法是self.dfs(grid, i, j 1)。3. BFS队列版与栈模拟DFS换种遍历顺序3.1 BFS的思路与代码DFS 是“一条路走到黑”BFS 则是“一层一层向外扩散”。BFS 更适合直观地模拟“水波扩散”的过程从一个陆地格子出发把它放进队列然后循环处理队列头部把它的四邻域中没走过的陆地格子加入队列尾部直到队列为空。好处是天然避免了递归调用不会出现系统递归栈溢出的问题在大网格下更稳妥。坏处是需要显式维护一个队列空间上略多一点点。下面是一版用队列实现的 BFSfrom collections import deque class Solution: def maxAreaOfIsland(self, grid: List[List[int]]) - int: max_area 0 rows, cols len(grid), len(grid[0]) directions [(1, 0), (-1, 0), (0, 1), (0, -1)] for i in range(rows): for j in range(cols): if grid[i][j] 1: # 当前岛屿面积 area 0 q deque() q.append((i, j)) grid[i][j] 0 # 入队前先标记沉岛 while q: x, y q.popleft() area 1 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 # 入队前标记防止重复入队 q.append((nx, ny)) max_area max(max_area, area) return max_areaBFS 版本有个细节值得单独拎出来说在把邻居加入队列的那一刻就把它改成 0而不是从队列里弹出来之后再去判断。这个细节特别容易踩坑。如果你入队时不标记等弹出时才标记那么同一个格子可能被多个邻居同时发现进入队列多次导致统计重复甚至队列里出现大量冗余数据影响性能。3.2 栈版DFS绕开递归栈溢出有些人问DFS 一定要递归吗不一定。递归的本质是系统帮你维护了一个调用栈你可以自己用显式栈来模拟这个过程这样既保留了 DFS 深度优先的特性又不依赖系统递归深度限制。用 Java 写栈版 DFSclass Solution { public int maxAreaOfIsland(int[][] grid) { int maxArea 0; int[] dx {1, -1, 0, 0}; int[] dy {0, 0, 1, -1}; for (int i 0; i grid.length; i) { for (int j 0; j grid[0].length; j) { if (grid[i][j] 1) { int area 0; Dequeint[] stack new ArrayDeque(); stack.push(new int[]{i, j}); grid[i][j] 0; while (!stack.isEmpty()) { int[] cur stack.pop(); area; for (int k 0; k 4; k) { int nx cur[0] dx[k]; int ny cur[1] dy[k]; if (nx 0 nx grid.length ny 0 ny grid[0].length grid[nx][ny] 1) { grid[nx][ny] 0; stack.push(new int[]{nx, ny}); } } } maxArea Math.max(maxArea, area); } } } return maxArea; } }这里面的Dequeint[]在 Java 里是双端队列用push和pop操作就等价于栈。如果你用LinkedList也可以但ArrayDeque在性能上更好不推荐用Stack类因为它继承自Vector内部有大量同步开销刷题时能避免就避免。3.3 三种写法对比这三种写法不是三选一的关系而是同一种图遍历思想在不同实现层面的映射实现方式递归深度/队列规模空间复杂度适用场景递归DFS最坏可能达到网格大小O(rows*cols)代码最简洁适合中小规模网格栈模拟DFS显式栈最坏也是网格大小O(rows*cols)避免系统栈溢出适合嵌套网格深队列BFS队列最坏接近网格大小O(rows*cols)直观模拟扩散过程同样无递归栈风险如果只是刷题我建议优先熟练掌握递归DFS因为代码最短、最不容易写错调试图也清晰。但在真实工程或超大规模网格场景中我更倾向 BFS 或栈版 DFS原因只有一个系统递归栈的深度通常只有几万层而一个 1000×1000 的网格如果全部是陆地递归深度可能达到百万量级直接 StackOverflow。4. 陆地沉没法空间复杂度O(1)的关键技巧4.1 原地标记的原理前面所有代码里都用到了同一个技巧遇到陆地格子立刻把它改成 0。这个操作我习惯叫“沉岛”它的本质是让当前格子“失去陆地属性”从而确保后续遍历不会再次把它当作起点或邻居。为什么要这样做而不是用一个 visited 二维数组因为 visited 数组会额外占用 O(rows*cols) 的空间。在 LeetCode 的很多题解里你会看到两种风格用 visited 的更“教科书”改原数组的更“实战”。这两种都没错但改原数组在空间复杂度和代码长度上都更优——你不用在循环里多写一次if (visited[i][j]) continue也不用在 DFS 的出口条件里多判断一个二维数组。“沉岛”相当于把问题变成了一张“逐渐消失的地图”每统计完一座岛屿这座岛屿就从地图上抹去剩下的遍历永远不会再碰到它。这既解决了重复计数的问题也保证了每个格子最多被访问常数次。4.2 常见误区忘了改状态导致死循环这个技巧用起来简单但有一个非常典型的错误在递归/队列处理的过程中先把相邻格子加入待处理列表等真正处理它时再去修改状态。这样会导致什么想象一下两个相邻的陆地格子 A 和 B。A 在扩展时发现 B把 B 加入队列此时没有标记 B。B 从队列弹出开始扩展发现 A 还没被标记于是又把 A 加入队列。A 再次弹出再次发现 B……整个程序就陷入无限循环。就算你运气好没有死循环同一个格子也会被加入队列多次面积统计重复。正确的做法是无论递归 DFS、栈 DFS 还是 BFS在“发现”这个格子时就要立刻标记它已经访问过。递归法里是把标记写在递归函数开头BFS 里是把标记写在入队前栈版里是把标记写在压栈前。这个“发现即标记”的原则是整道题最容易出错的地方没有之一。4.3 如果要保留原数组怎么办有些人会担心直接修改传入的 grid 会把原始数据破坏掉如果后面还有别的逻辑要用到这份网格怎么办这种顾虑是对的。力扣刷题时虽然不影响 AC但如果你做的是项目或者面试时和面试官讨论方案最好提一句“可以修改原数组如果不允许修改就用 visited 数组”。visited 写法就是在 DFS 函数里多一个参数private int dfs(int[][] grid, boolean[][] visited, int i, int j) { if (i 0 || i grid.length || j 0 || j grid[0].length || grid[i][j] 0 || visited[i][j]) { return 0; } visited[i][j] true; return 1 dfs(grid, visited, i - 1, j) dfs(grid, visited, i 1, j) dfs(grid, visited, i, j - 1) dfs(grid, visited, i, j 1); }两种方式的时间复杂度完全一样都是 O(rows*cols)区别只在空间上多了一个 visited 数组。我个人刷题时默认用沉岛因为力扣判题不会复用到你的输入数组沉岛写法代码更干净。5. 复杂度分析与95%用例都不会告诉你的边界坑5.1 时间与空间复杂度推演先看时间复杂度。主循环遍历了整个网格中的每一个格子这是 O(rowscols)。搜索过程中每个格子最多被进入一次——因为进入后就会被标记为 0。所以不管是 DFS 还是 BFS搜索部分的总工作量也是 O(rowscols)。整体时间复杂度就是 O(rows*cols)这是一个线性复杂度的算法不存在性能瓶颈。空间复杂度取决于搜索过程中使用的额外空间。递归 DFS 最坏情况下递归深度等于网格中陆地格子的数量比如整个网格全是陆地空间复杂度为 O(rowscols)。栈版和队列版的显式数据结构在最坏情况下也会存储大量格子同样是 O(rowscols)。如果使用原地沉岛法且不考虑递归栈额外空间甚至可以说 O(1)但分析递归算法时通常要把栈深度算进去。5.2 边界用例与空数组力扣给的测试用例一般不会刁难你但你自己写代码时一定要考虑两个极端空网格和单格子网格。如果 grid 长度为 0grid[0].length这行代码会直接抛出数组越界异常。所以进入函数后先判断if (grid null || grid.length 0) return 0;这个防御性写法在几乎所有网格类题目里都是标配。如果是 1×1 的网格且 grid[0][0] 1你的代码应该返回 1如果是 0应该返回 0。这个用例用来验证递归出口和主循环之间有没有逻辑漏洞。还有一个容易被忽略的边界DFS 里对grid[0].length的访问在行下标有效的前提下才安全。所以很多题解的出口顺序是“先判断行越界再判断列越界再判断值”这个顺序本身就是在保护grid[i]这一行数组是存在的。如果你把判断列越界写在行越界之前遇到非法 i 时grid[i]本身就已经越界了。5.3 大网格递归栈溢出的真实场景我在力扣上刷这道题时用递归 DFS 轻松过了。但后来自己做一个仿真数据实验生成了一张 2000×2000 全是陆地的网格再跑这段递归代码程序直接崩溃。这就是前面提到的系统递归栈深度限制每次递归调用要占用栈空间函数没有及时返回栈就一直增长最终溢出。这种情况下BFS 和显式栈 DFS 就显示出优势了。它们把“待访问状态”存在堆内存里而堆内存远大于栈内存。所以在写实战代码或面对超大输入时我强烈建议优先考虑非递归方案。如果你非要用递归可以考虑在语言层面调大递归栈比如 Python 里执行sys.setrecursionlimit(1000000)但这只是缓兵之计治标不治本。6. 从695延伸出去的岛屿问题家族6.1 岛屿数量200一样的模板刷完695之后你会发现自己已经顺手掌握了力扣 200 题“岛屿数量”。那道题要求返回岛屿总数而不是最大面积核心解法就是把695里的“累计面积”改成“每找到一座岛就 count”。代码改动不超过三行所以很多人会把这两道题放在同一天刷一次掌握两个知识点。// 岛屿数量核心代码 int count 0; for (int i 0; i grid.length; i) { for (int j 0; j grid[0].length; j) { if (grid[i][j] 1) { count; dfs(grid, i, j); // 把整座岛沉掉 } } }唯一的坑是 200 题里输入的字符是0和1如果你习惯用整数判断写grid[i][j] 1是永远不成立的这个问题我见过无数人在评论区吐槽。6.2 最大人工岛827与封闭岛屿1254695 的进阶版是 827 “最大人工岛”你最多可以把一个 0 改成 1问改造后能得到的最大岛屿面积是多少。这道题的常规做法是先用 DFS 给每座岛编号并记录面积然后再遍历每一个海洋格子把相邻岛屿的面积加在一起。你会发现695 里的“连通块统计”能力在这里变成了更复杂的“多连通块合并”的基石。1254 “统计封闭岛屿的数目”也很有意思它要求统计完全被水包围、不接触网格边界的岛屿。做法是在 695 的 DFS 过程中额外传递一个“是否碰到边界”的标志如果一座岛屿接触了网格边缘就不计数。这本质上是对 DFS 搜索过程的信息增强。6.3 刷题顺序建议如果你是从零开始刷岛屿问题我建议按这个顺序来695 岛屿的最大面积理解连通块与 DFS/BFS200 岛屿数量理解计数模式注意字符类型1254 统计封闭岛屿的数目理解边界条件对 DFS 的影响130 被围绕的区域理解逆向思维从边界反向深搜827 最大人工岛理解多连通块合并与编号技巧。这套顺序的好处是每道题都在前一道题的模板上增加一点点复杂度你不会产生“每道题都要从零开始”的挫败感。等五道题全部过一遍你基本就能认清这一类“网格图遍历”问题的所有套路了。回到 695 本身我个人做这道题最大的收获并不是学会了 DFS 怎么写而是真正理解了一个通用原则处理图遍历问题时与其纠结用哪种搜索方式不如先想清楚“如何保证每个节点只被处理一次”。标记时机、标记方式、搜索顺序所有代码细节都是围绕这一点展开的。这个原则不光适用于岛屿题你后面刷迷宫、矩阵路径、连通域分析等等都会反复用到它。最后分享一个我刷题时常用的自测技巧写完代码不要急着提交先在心里跑一遍 3×3 的全 1 网格预期结果是 9再跑一遍中间是 0 的 3×3 网格预期结果是 8最后跑一下全 0 网格预期结果是 0。这三个用例能在 10 秒内验证掉 80% 的常见错误比盲目提交省时多了。 力扣695岛屿最大面积：DFS/BFS与沉岛标记法图解
1. 题目拆解它到底在考什么1.1 题面速览与核心诉求力扣695题题目全称“岛屿的最大面积”是“岛屿问题”系列里非常经典的一道入门题。题面很简短给你一个二维网格 grid每个格子要么是 0代表水要么是 1代表陆地。水平或垂直方向上相邻的 1 连在一起构成一座岛屿。要求返回网格中面积最大的岛屿即最大的连续 1 的数量。这个题我第一次见到时第一反应是“这不就是数格子吗”确实它本质上就是数格子但难点在于如何把“连在一起的格子”正确地归为一组并且不重不漏地统计出每一组的数量。很多人一上来就直接双重循环遍历数组看到 1 就 count结果统计出来的根本不是岛屿面积而是全图一共有多少个陆地块。这就是没有理解“连通区域”这个核心概念。这道题的定位很精准它考察的是图的遍历具体来说是寻找无向图连通分量的最大大小。二维网格本身就是一张隐式的图每个格子是一个节点上下左右相邻的格子之间有一条边。你要做的就是找出所有连通分量记录它们的大小返回最大值。1.2 为什么说它是“连通分量”问题从数据结构的角度看grid 可以看作是图的一种邻接矩阵式表示。每个格子相当于一个节点四邻域上、下、左、右连接关系就是边。题目不允许斜对角相邻这非常重要很多初次接触的人容易把斜方向的格子也当成同一座岛屿然后面积就多算了。把问题抽象成连通分量后解法套路就清晰了遍历每一个格子当遇到一个未被访问过的 1 时从它出发把与之相连的所有 1 都找出来这个集合就是一个连通分量也就是一座岛屿。记录这个集合的大小继续遍历后面的格子直到整个网格扫描完成。这里有个关键点你需要注意一座岛屿只能被统计一次。如果每遇到一个 1 就去数一遍跟它相连的所有 1那么同一座岛屿里的每个 1 都会被当一次起点面积会重复计算多次结果会离谱到无法直视。解决办法是“标记已访问”这是所有岛屿类题目通用的解题框架。1.3 这类题的标准解题框架记一下这个模板它处理的不只是695题后面刷 200岛屿数量、130被围绕的区域、1254统计封闭岛屿的数目、827最大人工岛都能复用第一层循环遍历网格的每一个格子判断条件当前格子是陆地grid[i][j] 1并且没有被访问过扩展动作从当前格子出发向上下左右四个方向递归或队列扩展把相邻的陆地全部标记为已访问并统计数量更新答案每次找出一个岛屿后用它的面积更新最大面积。这套框架里面遍历方式可以选深度优先搜索DFS或广度优先搜索BFS标记方式可以选额外的 visited 数组也可以直接改原数组。不同的选择对应不同的写法和复杂度特点接下来我会逐个拆开讲。2. DFS递归版最直接的通解2.1 前置约定如何不走回头路DFS 的写法最贴合人脑的直觉站在一个陆地块上先把这个块算进当前岛屿的面积然后从它出发依次查看上下左右四个方向如果邻居也是陆地就继续走过去再重复“数自己、看邻居”的动作直到周围全是水或者边界才停下。这里最大的隐患是“回头路”。假设 A 的右边是 BB 的左边就是 A。你从 A 走到 B 之后如果不做任何标记B 检查左边邻居时又会走回 A然后再去右边、上边、下边两边互相反复横跳最终导致栈溢出。所以必须保证每个格子最多被“作为当前节点”处理一次。最简单的方式就是“沉岛”一旦访问过一个陆地格子立刻把它改成 0相当于让它沉到水下去后面这个格子就不再被当作陆地了。这个技巧很暴力但极其有效而且不需要额外的空间后面第4章我会专门分析。2.2 递归函数的四个出口写递归的 DFS 时函数开头一定是判断“当前格子能不能走”这是递归四要素里的终止条件。典型的判断顺序是行下标越界i 0 || i grid.length就返回 0列下标越界j 0 || j grid[0].length就返回 0当前格子是 0水就返回 0当前格子已经处理过如果用了 visited 数组会判断 visited[i][j]就返回 0。前两个是边界防护第三个是海洋防护第四个是防回头路防护。四个条件都过了这个格子才是真正可以走、需要数的陆地。只要有一个条件触发直接返回 0不再往下扩展。2.3 完整代码与逐行注释以 Java 写法为例这一版也是我刷题时最常写的class Solution { public int maxAreaOfIsland(int[][] grid) { int maxArea 0; for (int i 0; i grid.length; i) { for (int j 0; j grid[0].length; j) { // 每个格子都可能成为一座岛的起点 if (grid[i][j] 1) { // 从这个起点出发数出整座岛的面积 maxArea Math.max(maxArea, dfs(grid, i, j)); } } } return maxArea; } private int dfs(int[][] grid, int i, int j) { // 出口判断越界 or 水 or 已沉没 if (i 0 || i grid.length || j 0 || j grid[0].length || grid[i][j] 0) { return 0; } // 沉岛避免回头路同时让这个格子不再被统计 grid[i][j] 0; // 当前这一格算 1再加上四个方向的递归结果 return 1 dfs(grid, i - 1, j) dfs(grid, i 1, j) dfs(grid, i, j - 1) dfs(grid, i, j 1); } }这段代码里return 1 dfs(上) dfs(下) dfs(左) dfs(右)是整个 DFS 的核心表达式。它把当前格子的面积 1 和四个方向探索到的所有陆地面积累加在一起。每次递归调用返回的是“以这个格子为起点能到达的一片陆地”的大小。用 Python 写也差不多class Solution: def maxAreaOfIsland(self, grid: List[List[int]]) - int: max_area 0 rows, cols len(grid), len(grid[0]) for i in range(rows): for j in range(cols): if grid[i][j] 1: max_area max(max_area, self.dfs(grid, i, j)) return max_area def dfs(self, grid, i, j): if i 0 or i len(grid) or j 0 or j len(grid[0]) or grid[i][j] 0: return 0 grid[i][j] 0 return 1 self.dfs(grid, i - 1, j) self.dfs(grid, i 1, j) \ self.dfs(grid, i, j - 1) self.dfs(grid, i, j - 1) # 注意这里等等Python 版里的 j 1 方向如果手误写成了 j - 1左右方向就会被重复计算左边会被数两遍右边不会去导致面积偏大。这是复制粘贴类错误里非常典型的一种写完后务必检查四个方向的坐标变化。正确写法是self.dfs(grid, i, j 1)。3. BFS队列版与栈模拟DFS换种遍历顺序3.1 BFS的思路与代码DFS 是“一条路走到黑”BFS 则是“一层一层向外扩散”。BFS 更适合直观地模拟“水波扩散”的过程从一个陆地格子出发把它放进队列然后循环处理队列头部把它的四邻域中没走过的陆地格子加入队列尾部直到队列为空。好处是天然避免了递归调用不会出现系统递归栈溢出的问题在大网格下更稳妥。坏处是需要显式维护一个队列空间上略多一点点。下面是一版用队列实现的 BFSfrom collections import deque class Solution: def maxAreaOfIsland(self, grid: List[List[int]]) - int: max_area 0 rows, cols len(grid), len(grid[0]) directions [(1, 0), (-1, 0), (0, 1), (0, -1)] for i in range(rows): for j in range(cols): if grid[i][j] 1: # 当前岛屿面积 area 0 q deque() q.append((i, j)) grid[i][j] 0 # 入队前先标记沉岛 while q: x, y q.popleft() area 1 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 # 入队前标记防止重复入队 q.append((nx, ny)) max_area max(max_area, area) return max_areaBFS 版本有个细节值得单独拎出来说在把邻居加入队列的那一刻就把它改成 0而不是从队列里弹出来之后再去判断。这个细节特别容易踩坑。如果你入队时不标记等弹出时才标记那么同一个格子可能被多个邻居同时发现进入队列多次导致统计重复甚至队列里出现大量冗余数据影响性能。3.2 栈版DFS绕开递归栈溢出有些人问DFS 一定要递归吗不一定。递归的本质是系统帮你维护了一个调用栈你可以自己用显式栈来模拟这个过程这样既保留了 DFS 深度优先的特性又不依赖系统递归深度限制。用 Java 写栈版 DFSclass Solution { public int maxAreaOfIsland(int[][] grid) { int maxArea 0; int[] dx {1, -1, 0, 0}; int[] dy {0, 0, 1, -1}; for (int i 0; i grid.length; i) { for (int j 0; j grid[0].length; j) { if (grid[i][j] 1) { int area 0; Dequeint[] stack new ArrayDeque(); stack.push(new int[]{i, j}); grid[i][j] 0; while (!stack.isEmpty()) { int[] cur stack.pop(); area; for (int k 0; k 4; k) { int nx cur[0] dx[k]; int ny cur[1] dy[k]; if (nx 0 nx grid.length ny 0 ny grid[0].length grid[nx][ny] 1) { grid[nx][ny] 0; stack.push(new int[]{nx, ny}); } } } maxArea Math.max(maxArea, area); } } } return maxArea; } }这里面的Dequeint[]在 Java 里是双端队列用push和pop操作就等价于栈。如果你用LinkedList也可以但ArrayDeque在性能上更好不推荐用Stack类因为它继承自Vector内部有大量同步开销刷题时能避免就避免。3.3 三种写法对比这三种写法不是三选一的关系而是同一种图遍历思想在不同实现层面的映射实现方式递归深度/队列规模空间复杂度适用场景递归DFS最坏可能达到网格大小O(rows*cols)代码最简洁适合中小规模网格栈模拟DFS显式栈最坏也是网格大小O(rows*cols)避免系统栈溢出适合嵌套网格深队列BFS队列最坏接近网格大小O(rows*cols)直观模拟扩散过程同样无递归栈风险如果只是刷题我建议优先熟练掌握递归DFS因为代码最短、最不容易写错调试图也清晰。但在真实工程或超大规模网格场景中我更倾向 BFS 或栈版 DFS原因只有一个系统递归栈的深度通常只有几万层而一个 1000×1000 的网格如果全部是陆地递归深度可能达到百万量级直接 StackOverflow。4. 陆地沉没法空间复杂度O(1)的关键技巧4.1 原地标记的原理前面所有代码里都用到了同一个技巧遇到陆地格子立刻把它改成 0。这个操作我习惯叫“沉岛”它的本质是让当前格子“失去陆地属性”从而确保后续遍历不会再次把它当作起点或邻居。为什么要这样做而不是用一个 visited 二维数组因为 visited 数组会额外占用 O(rows*cols) 的空间。在 LeetCode 的很多题解里你会看到两种风格用 visited 的更“教科书”改原数组的更“实战”。这两种都没错但改原数组在空间复杂度和代码长度上都更优——你不用在循环里多写一次if (visited[i][j]) continue也不用在 DFS 的出口条件里多判断一个二维数组。“沉岛”相当于把问题变成了一张“逐渐消失的地图”每统计完一座岛屿这座岛屿就从地图上抹去剩下的遍历永远不会再碰到它。这既解决了重复计数的问题也保证了每个格子最多被访问常数次。4.2 常见误区忘了改状态导致死循环这个技巧用起来简单但有一个非常典型的错误在递归/队列处理的过程中先把相邻格子加入待处理列表等真正处理它时再去修改状态。这样会导致什么想象一下两个相邻的陆地格子 A 和 B。A 在扩展时发现 B把 B 加入队列此时没有标记 B。B 从队列弹出开始扩展发现 A 还没被标记于是又把 A 加入队列。A 再次弹出再次发现 B……整个程序就陷入无限循环。就算你运气好没有死循环同一个格子也会被加入队列多次面积统计重复。正确的做法是无论递归 DFS、栈 DFS 还是 BFS在“发现”这个格子时就要立刻标记它已经访问过。递归法里是把标记写在递归函数开头BFS 里是把标记写在入队前栈版里是把标记写在压栈前。这个“发现即标记”的原则是整道题最容易出错的地方没有之一。4.3 如果要保留原数组怎么办有些人会担心直接修改传入的 grid 会把原始数据破坏掉如果后面还有别的逻辑要用到这份网格怎么办这种顾虑是对的。力扣刷题时虽然不影响 AC但如果你做的是项目或者面试时和面试官讨论方案最好提一句“可以修改原数组如果不允许修改就用 visited 数组”。visited 写法就是在 DFS 函数里多一个参数private int dfs(int[][] grid, boolean[][] visited, int i, int j) { if (i 0 || i grid.length || j 0 || j grid[0].length || grid[i][j] 0 || visited[i][j]) { return 0; } visited[i][j] true; return 1 dfs(grid, visited, i - 1, j) dfs(grid, visited, i 1, j) dfs(grid, visited, i, j - 1) dfs(grid, visited, i, j 1); }两种方式的时间复杂度完全一样都是 O(rows*cols)区别只在空间上多了一个 visited 数组。我个人刷题时默认用沉岛因为力扣判题不会复用到你的输入数组沉岛写法代码更干净。5. 复杂度分析与95%用例都不会告诉你的边界坑5.1 时间与空间复杂度推演先看时间复杂度。主循环遍历了整个网格中的每一个格子这是 O(rowscols)。搜索过程中每个格子最多被进入一次——因为进入后就会被标记为 0。所以不管是 DFS 还是 BFS搜索部分的总工作量也是 O(rowscols)。整体时间复杂度就是 O(rows*cols)这是一个线性复杂度的算法不存在性能瓶颈。空间复杂度取决于搜索过程中使用的额外空间。递归 DFS 最坏情况下递归深度等于网格中陆地格子的数量比如整个网格全是陆地空间复杂度为 O(rowscols)。栈版和队列版的显式数据结构在最坏情况下也会存储大量格子同样是 O(rowscols)。如果使用原地沉岛法且不考虑递归栈额外空间甚至可以说 O(1)但分析递归算法时通常要把栈深度算进去。5.2 边界用例与空数组力扣给的测试用例一般不会刁难你但你自己写代码时一定要考虑两个极端空网格和单格子网格。如果 grid 长度为 0grid[0].length这行代码会直接抛出数组越界异常。所以进入函数后先判断if (grid null || grid.length 0) return 0;这个防御性写法在几乎所有网格类题目里都是标配。如果是 1×1 的网格且 grid[0][0] 1你的代码应该返回 1如果是 0应该返回 0。这个用例用来验证递归出口和主循环之间有没有逻辑漏洞。还有一个容易被忽略的边界DFS 里对grid[0].length的访问在行下标有效的前提下才安全。所以很多题解的出口顺序是“先判断行越界再判断列越界再判断值”这个顺序本身就是在保护grid[i]这一行数组是存在的。如果你把判断列越界写在行越界之前遇到非法 i 时grid[i]本身就已经越界了。5.3 大网格递归栈溢出的真实场景我在力扣上刷这道题时用递归 DFS 轻松过了。但后来自己做一个仿真数据实验生成了一张 2000×2000 全是陆地的网格再跑这段递归代码程序直接崩溃。这就是前面提到的系统递归栈深度限制每次递归调用要占用栈空间函数没有及时返回栈就一直增长最终溢出。这种情况下BFS 和显式栈 DFS 就显示出优势了。它们把“待访问状态”存在堆内存里而堆内存远大于栈内存。所以在写实战代码或面对超大输入时我强烈建议优先考虑非递归方案。如果你非要用递归可以考虑在语言层面调大递归栈比如 Python 里执行sys.setrecursionlimit(1000000)但这只是缓兵之计治标不治本。6. 从695延伸出去的岛屿问题家族6.1 岛屿数量200一样的模板刷完695之后你会发现自己已经顺手掌握了力扣 200 题“岛屿数量”。那道题要求返回岛屿总数而不是最大面积核心解法就是把695里的“累计面积”改成“每找到一座岛就 count”。代码改动不超过三行所以很多人会把这两道题放在同一天刷一次掌握两个知识点。// 岛屿数量核心代码 int count 0; for (int i 0; i grid.length; i) { for (int j 0; j grid[0].length; j) { if (grid[i][j] 1) { count; dfs(grid, i, j); // 把整座岛沉掉 } } }唯一的坑是 200 题里输入的字符是0和1如果你习惯用整数判断写grid[i][j] 1是永远不成立的这个问题我见过无数人在评论区吐槽。6.2 最大人工岛827与封闭岛屿1254695 的进阶版是 827 “最大人工岛”你最多可以把一个 0 改成 1问改造后能得到的最大岛屿面积是多少。这道题的常规做法是先用 DFS 给每座岛编号并记录面积然后再遍历每一个海洋格子把相邻岛屿的面积加在一起。你会发现695 里的“连通块统计”能力在这里变成了更复杂的“多连通块合并”的基石。1254 “统计封闭岛屿的数目”也很有意思它要求统计完全被水包围、不接触网格边界的岛屿。做法是在 695 的 DFS 过程中额外传递一个“是否碰到边界”的标志如果一座岛屿接触了网格边缘就不计数。这本质上是对 DFS 搜索过程的信息增强。6.3 刷题顺序建议如果你是从零开始刷岛屿问题我建议按这个顺序来695 岛屿的最大面积理解连通块与 DFS/BFS200 岛屿数量理解计数模式注意字符类型1254 统计封闭岛屿的数目理解边界条件对 DFS 的影响130 被围绕的区域理解逆向思维从边界反向深搜827 最大人工岛理解多连通块合并与编号技巧。这套顺序的好处是每道题都在前一道题的模板上增加一点点复杂度你不会产生“每道题都要从零开始”的挫败感。等五道题全部过一遍你基本就能认清这一类“网格图遍历”问题的所有套路了。回到 695 本身我个人做这道题最大的收获并不是学会了 DFS 怎么写而是真正理解了一个通用原则处理图遍历问题时与其纠结用哪种搜索方式不如先想清楚“如何保证每个节点只被处理一次”。标记时机、标记方式、搜索顺序所有代码细节都是围绕这一点展开的。这个原则不光适用于岛屿题你后面刷迷宫、矩阵路径、连通域分析等等都会反复用到它。最后分享一个我刷题时常用的自测技巧写完代码不要急着提交先在心里跑一遍 3×3 的全 1 网格预期结果是 9再跑一遍中间是 0 的 3×3 网格预期结果是 8最后跑一下全 0 网格预期结果是 0。这三个用例能在 10 秒内验证掉 80% 的常见错误比盲目提交省时多了。