题目刚出来的时候我第一个想法就是暴力把每个0改成1然后跑一遍BFS/DFS算最大连通面积。好在马上算了一笔账——矩阵最大300乘300格子数9万最坏情况遍历每个0再扫一遍全图复杂度直接奔着十亿量级去在LeetCode上想不超时基本是做梦。后来用DeepSeek帮我把思路顺了一遍才真正吃透这题的核心不用真的修改每个格子而是把图先预处理成若干个标号的岛屿块再枚举每个0去拼接它四周的岛屿面积。这题在LeetCode上是827题名字叫最大人工岛输入是int[][] grid值是0或1目标是把一个0改成1后让上下左右相邻的1组成最大的连通区域返回最大面积。别看描述只有一句话它在面试里可是个高频的图论题既能考DFS/BFS基本功又能考预处理降低复杂度的优化意识。这篇就把我的完整思路、Java实现、以及当时怎么用DeepSeek帮我审查边界情况的过程都摆出来给准备面试和刷图论题的朋友做个参考。1. 题目核心与两种常见的错误思路1.1 为什么暴力修改会超时先定义清楚问题。grid[i][j]属于[0,1]所谓人工岛就是你可以把恰好一个0的位置改成1然后看整个矩阵里由上下左右四个方向相连的1构成的最大连通块面积。注意是恰好一个0不能不改所以答案至少是1哪怕整个矩阵全是0也是把某个0翻成1后面积为1。最容易想到的暴力做法就是遍历每个0把它临时改成1然后以这个格子为起点做一次DFS统计连通面积统计完再改回去。这样最坏情况是O(N^2 * N^2)N是边长300的矩阵跑下来要81亿次操作LeetCode的判定服务器再快也扛不住。这里有个关键认知每次DFS都会重复扫描大量已经访问过的大块1这些重复计算是完全可以免掉的。还有一种容易踩的坑是只算某个0四周的1的个数加1。比如一个0上下左右各贴着一个大岛简单相加会重复计算因为上下两个方向可能属于同一个连通块。如果不做去重结果会偏大如果只统计不同连通块的数量又可能漏掉那些通过其他路径连过来的区域。所以我后来确定的方向是先把所有连通块染色编号再枚举0做拼接。1.2 预处理染色为什么能降复杂度预处理染色的思路很直白对整个矩阵做一次遍历每遇到一个没访问过的1就用DFS/BFS给它标记一个唯一的编号比如从2开始同时用一个HashMap记录这个编号对应的连通块面积。这样一趟下来矩阵里每个1都知道自己属于哪个岛每个岛的area也存好了。之后枚举每个0的时候只需要看它上下左右四个邻居的编号把这些编号去重后对应的面积相加再加1这个0本身翻转成1就是把这个0变成陆地后的连通面积。这样做的时间复杂度是O(N^2)加一次(DFS总耗时也是O(N^2))枚举0整体O(N^2)N最大300最多9万次操作完全不同量级。这个先染色、再拼接的思路本质上和并查集的连通分量思想是一回事只是DFS染色更直接代码也更好写。我下面这份实现就是基于这个思路并且在实际跑的时候通过DeepSeek帮我补了好几个容易漏的边界判断。2. 基于DFS染色与枚举拼接的完整Java实现2.1 核心代码与逐段说明先放下我的AC代码用的就是DFS染色HashMap记录面积枚举0去重拼接class Solution { private int n; private int[][] grid; private MapInteger, Integer areaMap new HashMap(); private int[][] dirs {{1,0},{-1,0},{0,1},{0,-1}}; public int largestIsland(int[][] grid) { this.grid grid; this.n grid.length; int color 2; int maxArea 0; boolean hasZero false; // 第一遍给每个连通块染色并记录面积 for (int i 0; i n; i) { for (int j 0; j n; j) { if (grid[i][j] 1) { int area dfs(i, j, color); areaMap.put(color, area); maxArea Math.max(maxArea, area); color; } else if (grid[i][j] 0) { hasZero true; } } } // 如果没有0说明全是1最大面积就是整个矩阵 if (!hasZero) { return n * n; } // 第二遍枚举每个0拼接四周岛屿面积 for (int i 0; i n; i) { for (int j 0; j n; j) { if (grid[i][j] 0) { SetInteger visitedColor new HashSet(); int cur 1; for (int[] d : dirs) { int ni i d[0]; int nj j d[1]; if (ni 0 ni n nj 0 nj n grid[ni][nj] 1) { int c grid[ni][nj]; if (visitedColor.add(c)) { cur areaMap.get(c); } } } maxArea Math.max(maxArea, cur); } } } return maxArea; } private int dfs(int i, int j, int color) { if (i 0 || i n || j 0 || j n || grid[i][j] ! 1) { return 0; } grid[i][j] color; int area 1; for (int[] d : dirs) { area dfs(i d[0], j d[1], color); } return area; } }这里有几个细节我挨个说。第一为什么染色从2开始因为grid里0和1已经占用了如果从2开始染色那么后续判断邻居是不是染色过的岛屿就很简单只要grid[ni][nj] 1就说明它是某个被染色的连通块。如果强行用别的标记方式比如额外开一个visited数组代码会啰嗦很多。第二为什么第二遍枚举0的时候要用一个HashSet去重因为同一个岛屿可能同时出现在这个0的上方和左侧比如这个0被一个大C形岛屿三面包围如果不去重同一个岛的面积会被加两次。我一开始就没加去重拿示例数据跑出来是错的就是重复统计岛屿这个坑。第三DFS里为什么要先判断grid[i][j] ! 1而不是加一个单独的visited数组因为染色后grid本身的值就不再是1了染成color后再次访问时grid[i][j]不等于1自然被拦截。这样就不需要额外开辟visited矩阵也避免了忘记重置visited导致重复染色这种常见错误。2.2 复杂度分析与空间使用情况这个解法的时间复杂度很好算。第一遍遍历所有格子DFS染色每个格子最多被访问常数次O(N^2)。第二遍遍历所有0格子每个0最多查4个方向用HashSet去重每个方向O(1)处理也是O(N^2)。总时间复杂度O(N^2)。空间上递归调用栈在最坏情况下整个矩阵全是1深度为N^2也就是9万层这不是一个可以忽略的问题。我后面会专门讲如何把DFS改成迭代栈以及为什么在实际面试中要注意递归深度。areaMap的键值对数量等于连通块数量最坏情况是棋盘式交错分布每个1都是独立岛屿最多约N^2/2个键值对这个内存是OK的。HashSet只在一个0的枚举内使用每个0的处理里申请一次空间O(1)级别。总体来说空间O(N^2)和输入规模一致。3. 用DeepSeek辅助分析时的隐藏收获3.1 让AI帮忙构造边界测试用例代码写完后我没有直接提交而是又用DeepSeek做了一轮代码审查。我给它看的是我第一版的代码其实就是上面这份但当时第一个判断里我没有if (!hasZero) return n * n;这个分支。DeepSeek直接指出如果整个矩阵全是1你在第二遍枚举0的时候找不到任何一个0maxArea只能停留在第一遍染色时算出来的n*n其实也能返回正确值但万一某次我把maxArea初始化为0且在循环前就先返回了就会出错。所以我加了显式的hasZero判断这也让代码逻辑更清晰。另外它帮我列了一组特别容易出错的测试用例grid [[1]]只有一个格子答案是1。因为这个1不用翻转最大人工岛只能是1。grid [[0]]只有一个0翻成1后答案是1。grid [[1,0],[0,1]]两个对角线方向的1不相邻翻任何一个0都只能连一个岛答案是2。grid [[1,1],[1,0]]三个1围着一个0翻0后面积是4。grid [[1,0],[1,0]]翻右边的0可以连接左边竖着的两个1答案是3但如果只统计上下左右不连通的话可能算成2这里最能验证去重逻辑。我把这些用例手动跑了一遍AC之后又去LeetCode官方题解区看了一眼确认了这题还有一种并查集解法两种解法都能过。但对我来说DFS染色方案更直观面试时讲思路也更快。3.2 DeepSeek还能做什么复杂度讲解与代码风格优化在等代码跑测试的时候我让DeepSeek用最白的话解释一遍这个解法为什么高效。它的解释让我印象很深这就好比你先给每个岛发一张身份证记录每张身份证对应多少人后面想知道把一块海填了能连多少人只需要看周围有几张不同的身份证把对应人数加起来就行不用再重新数一遍整个岛上的人。这种类比让我在面试表述时特别受用。以前我讲算法题总喜欢堆术语比如动态规划连通分量面试官当然听得懂但不一定能快速get到你真正的优化点。现在我会先讲这个身份证的类比再补充一句本质上是对每个连通块做预处理标记用空间换时间效果明显更好。另外DeepSeek还帮我把原本写的四层if嵌套的DFS简写成一段带方向数组的递归代码可读性提升了不少。最开始我写的DFS是这样的private int dfs(int i, int j, int color) { if (i 0 || i n || j 0 || j n || grid[i][j] ! 1) { return 0; } grid[i][j] color; return 1 dfs(i - 1, j, color) dfs(i 1, j, color) dfs(i, j - 1, color) dfs(i, j 1, color); }这代码本身没问题但方向枚举重复写四遍容易在复制粘贴时漏掉一个改变量。用dirs数组之后新增方向只改数组就行代码也更紧凑。这种小优化看起来不起眼但在白板面试时能降低手误的概率。4. 面试现场如何一步步推导这题4.1 五分钟内建立暴力到优化的思维路径如果面试官现场抛给你这题我建议你先别急着写代码按下面这个顺序在脑子里过一遍第一步明确操作只能翻一个0。第二步最朴素的想法枚举所有0翻它算最大连通面积。这是O(N^4)先说给面试官听表示你理解了问题的暴力解。第三步观察冗余每个连通块内部的1会被重复扫描无数次。如果先算好每个连通块的面积问题就变成了枚举0拼接不同编号的连通块面积。第四步选择实现工具DFS/BFS染色或者并查集。二者时间复杂度相同DFS染色写起来更直观。第五步考虑特殊情况全是0、全是1、单行单列、岛包围海、海包围岛等。这套思路可以在几分钟内说完而且每一步都有充分的理由。面试官最怕的不是你写不出最优解而是你一上来就闷头写并查集问你怎么想到的你说我做过原题。所以哪怕你最终使用的是并查集也一定要把从暴力到预处理的优化过程讲清楚。4.2 从DFS染色到并查集的迁移这里多说一句并查集的写法因为很多大厂面试官会追问还有没有别的实现方式。并查集的思路是遍历所有1的格子如果它右边和下边的邻居也是1就Union这两个格子同时用另一个数组维护每个连通块的大小。最后同样是枚举0查找它四个方向邻居所在集合的根用HashSet去重后累加集合大小再加1。两种方法本质一样但并查集的代码量要更大而且需要额外维护parent数组和size数组。DFS染色方案只需要原位修改grid值空间更省。不过当你需要频繁动态合并多个区域时并查集才是更好的选择比如后续有多次填海造岛操作时DFS染色就要重新跑一遍。面试时如果能说出这两种方案的适用场景差异是非常加分的。5. 常见问题与调试实录5.1 为什么用HashSet去重后结果还是不对这是我调试时最崩溃的一个问题。代码逻辑看起来完全正确上下左右四个方向取邻居的color放进HashSet然后累加。但我第一次跑的时候遇到一个回字形用例给我算出了离谱的大数。后来仔细排查发现我的DFS染色函数里写的是grid[i][j] color;但后面在枚举0时我用的判断条件是grid[ni][nj] ! 0 grid[ni][nj] ! 1这其实会把原值为1但还没被染色的格子也当成一个独立color而该color可能不在areaMap里导致空指针异常或者相加出的面积是错的。正确做法是判断grid[ni][nj] 1因为只有染色过的格子才会大于1。这里有个容易让人迷惑的点第一遍染色结束后grid里已经不存在值为1的格子了所有原值为1的格子要么被染成2、3、4等要么因为DFS没访问到理论上不会发生因为我们遍历所有格子时遇到了1就染色所以第二遍枚举0时只要碰到大于1的值必然是合法岛屿编号。如果你用! 0这种判断恰好会访问到一些尚未染色但值为1的格子如果代码有bug导致某些1没被染色表面看起来没错实际上掩盖了问题。5.2 递归深度导致栈溢出一个300x300全1矩阵引发的血案我前面提到过最坏情况下DFS递归深度等于连通块大小整个矩阵全是1时DFS会一直递归到最后一层才回头深度是9万。Java默认栈大小通常在1MB左右9万层的递归在LeetCode上就可能爆栈。我自己的实测是在本地IDE里跑300x300全1矩阵直接StackOverflowError。解决办法有两个。一是改用显式的栈Stack或Deque做迭代DFS代码稍微长一点但绝对安全二是先判断特例如果整个矩阵没有0那答案就是n*n可以直接返回。这个特判不光能防爆栈还能提升性能。对应到代码里就是我加的hasZero分支。但注意如果矩阵是999个1加1个0DFS深度也会接近9万特判解决不了所有情况。所以更稳妥的解法是把DFS改成BFS或者迭代栈。我后来专门写了一个迭代DFS版本备用private int dfsIterative(int startI, int startJ, int color) { Dequeint[] stack new ArrayDeque(); stack.push(new int[]{startI, startJ}); int area 0; while (!stack.isEmpty()) { int[] cur stack.pop(); int i cur[0], j cur[1]; if (i 0 || i n || j 0 || j n || grid[i][j] ! 1) { continue; } grid[i][j] color; area; for (int[] d : dirs) { stack.push(new int[]{i d[0], j d[1]}); } } return area; }这里有个小细节用ArrayDeque的push/pop方法模拟栈比用Stack类性能更好因为Stack继承了Vector有同步开销。当然你也可以用LinkedList当栈但ArrayDeque在随机访问和内存局部性上都更好。这个迭代版本在LeetCode上跑300x300的全1矩阵毫无压力。5.3 枚举0时要注意的重复岛屿拼接问题假设有这样的场景一个0的左边和上边都属于同一个连通块但因为位置不同它们的color编号相同。如果你直接把四个方向各自的面积都加起来就会把同一个岛的面积重复计算。比如矩阵1 1 0 1 0 1 1 1 1中间这个0上下左右分别属于两个不同的岛吗并不是。它的左、上、下都属于那个外圈大岛的一部分只是从0的位置看左、上、下是不同的邻居格子但它们在染色后都拥有同一个编号。如果不加HashSet去重会被算成左3 上3 下3 1 10而实际翻完这个0后它只会连接外圈大岛和右边小岛总面积是外圈面积加内圈面积加1。加了HashSet之后第一次遇到某个color就累加它的面积之后再遇到相同color就跳过这样得到的才是真实拼接面积。这个坑非常经典很多题解都会专门提到但自己写的时候还是容易犯因为视觉上你会觉得上下左右四个方向肯定是四个不同的岛其实不是。6. 从这题延伸出去的刷题与面试准备建议6.1 岛屿类题型的通用套路最大人工岛并不是一个孤立的题它和LeetCode上的岛屿数量、最大岛屿面积、被围绕的区域等题是一族。做这类题的核心就是连通块遍历。我建议你把下面的模板记牢遍历二维数组遇到未被访问的陆地。以该陆地为起点做DFS或BFS将访问过的格子标记为已访问。在遍历过程中统计面积、数量或其他指标。最大人工岛比基础岛屿题多了一步枚举0并拼接多个连通块但基础模板完全复用。所以如果你还没做过岛屿数量先去做那题再回来做827会顺畅很多。凡是上下左右相邻的连通性问题都可以用这个套路。面试时如果时间充裕你可以主动提一句这题理论上也可以用并查集做DFS染色方案在多次查询时可能不如并查集但单次求解场景下两者复杂度相同。 这能展现你懂多种数据结构的适用边界。6.2 用DeepSeek刷题的正确姿势我最近刷题习惯先自己写一版然后让DeepSeek当代码审查员。具体用法是把代码粘贴给它再附上题目链接问它找出我代码里的边界条件漏洞或者这个解法还能不能优化。实测下来DeepSeek对常见题型的分析很靠谱尤其擅长解释为什么这个测试用例会挂和如何构造边界用例。但有两个注意点一是不要直接让它给完整答案那样你学不到东西二是它给出的代码偶尔会有细节错误比如方向数组少写一个方向你必须自己能看懂并纠正。如果想让DeepSeek帮你做错题分析可以这样提问我这段代码在输入[[1,1,0],[1,0,1],[1,1,1]]时返回10正确答案是7问题可能出在哪 它会很快定位到重复统计多个邻居属于同一岛屿的问题。这种交互方式比一个人对着报错发呆高效得多。6.3 在真实项目中最大人工岛能用来做什么这题虽然看起来很竞赛但它的思想在生产环境里并不少见。比如在图像处理里连通域标记Connected Component Labeling就是一模一样的操作把像素值为1的区域标为不同的编号然后统计面积、外接矩形、质心等特征。OpenCV里的connectedComponents函数就是这么实现的。再比如地图导航里的可达区域分析你把障碍物标记为0可通行区域标记为1找出所有连通区域如果某个障碍物被移除相当于0变1能打开多大的连通区域这就是如果炸掉一堵墙最大能打通多少个房间的规划问题。所以刷这道题不只是为了过面试它背后的连通域标记是非常基础的算法能力。7. 我的最终体会与一个小技巧这题我前前后后写了三个版本第一版暴力超时第二版DFS染色递归全1矩阵栈溢出第三版迭代DFSHashSet去重AC。整个过程最有价值的不是最终代码而是我学会了在动手前先想清楚哪些计算可以预处理。很多二维矩阵题都是这个套路先扫一遍记录信息再扫一遍使用信息复杂度从O(N^4)降到O(N^2)。最后分享一个调试小技巧当你不确定某个矩阵题的正确性时把grid直接打印出来用不同数字代表不同岛屿的编号眼睛比代码更容易发现问题。我在验证染色是否成功时就特别喜欢看控制台里那些排列整齐的2、3、4哪一片没染上色一眼就能看出来。拿到这道题的朋友如果第一遍就AC了说明你的DFS和去重意识已经很扎实如果踩了我提到的那几个坑也别灰心这类预处理枚举的思维多练几道题就会变成肌肉记忆。