算法题最大人工岛-平芜编程栈

827. 最大人工岛

问题描述

给你一个大小为n x n的二进制矩阵grid，其中0表示海洋，1表示陆地。

你可以将恰好一个海洋格子（即0）变为陆地（即1）。

返回执行此操作后，矩阵中最大岛屿面积。岛屿是由 4 个方向上相连的1形成的。

示例：

输入:grid=[[1,0],[0,1]]输出:3解释:将 grid[0][1]变为1，可形成面积为3的岛屿。

输入:grid=[[1,1],[1,0]]输出:4解释:将 grid[1][0]变为1，整个矩阵变成一个面积为4的岛屿。

输入:grid=[[1,1],[1,1]]输出:4解释:矩阵中已经没有海洋格子，最大岛屿面积为4。

算法思路

岛屿编号标记：

遍历所有陆地，计算每个独立岛屿的面积
- 使用 DFS/BFS 遍历每个未访问的陆地格子
- 为每个岛屿分配唯一的编号（从 2 开始，避免与原始的 0、1 冲突）
- 记录每个编号对应的岛屿面积
遍历所有海洋格子，模拟填海操作
- 对于每个海洋格子 (0)，检查其四个方向相邻的岛屿
- 使用 Set 去重，避免重复计算同一个岛屿
- 计算填海后可能形成的最大岛屿面积（1 + 所有相邻不同岛屿面积之和）
边界情况处理：
- 如果矩阵中全是陆地，直接返回总面积
- 如果矩阵中全是海洋，返回 1（填一个格子）

代码实现

classSolution{// 方向数组：上下左右四个方向privatestaticfinalint[][]DIRECTIONS={{-1,0},{1,0},{0,-1},{0,1}};/** * 计算将一个海洋格子变为陆地后的最大岛屿面积 * * @param grid n x n 的二进制矩阵，0表示海洋，1表示陆地 * @return 最大岛屿面积 */publicintlargestIsland(int[][]grid){intn=grid.length;// 岛屿编号从2开始（避免与原始的0、1冲突）intislandId=2;// 记录每个岛屿编号对应的面积Map<Integer,Integer>islandArea=newHashMap<>();// 遍历所有格子，识别并标记所有岛屿for(inti=0;i<n;i++){for(intj=0;j<n;j++){// 如果当前格子是陆地（值为1），开始DFS计算岛屿面积if(grid[i][j]==1){intarea=dfs(grid,i,j,islandId);islandArea.put(islandId,area);islandId++;// 为下一个岛屿准备新的编号}}}// 初始化结果为当前最大岛屿面积（不进行填海操作的情况）intmaxArea=0;for(intarea:islandArea.values()){maxArea=Math.max(maxArea,area);}// 遍历所有海洋格子，模拟填海操作for(inti=0;i<n;i++){for(intj=0;j<n;j++){// 只处理海洋格子（值为0）if(grid[i][j]==0){// 使用Set记录相邻的不同岛屿编号，避免重复计算Set<Integer>neighborIslands=newHashSet<>();// 检查四个方向的相邻格子for(int[]dir:DIRECTIONS){intni=i+dir[0];intnj=j+dir[1];// 检查边界条件if(ni>=0&&ni<n&&nj>=0&&nj<n){// 如果相邻格子是陆地（编号>=2），加入Setif(grid[ni][nj]>=2){neighborIslands.add(grid[ni][nj]);}}}// 计算填海后的总面积：1（新填的格子）+ 所有相邻岛屿面积之和inttotalArea=1;for(intid:neighborIslands){totalArea+=islandArea.get(id);}maxArea=Math.max(maxArea,totalArea);}}}returnmaxArea;}/** * 深度优先搜索，计算岛屿面积并标记岛屿编号 * * @param grid 网格矩阵 * @param row 当前行坐标 * @param col 当前列坐标 * @param islandId 当前岛屿的编号 * @return 岛屿的面积 */privateintdfs(int[][]grid,introw,intcol,intislandId){intn=grid.length;// 边界检查：超出边界或不是陆地（原始值为1）if(row<0||row>=n||col<0||col>=n||grid[row][col]!=1){return0;}// 标记当前格子为当前岛屿编号grid[row][col]=islandId;// 初始化面积为1（当前格子）intarea=1;// 递归遍历四个方向的相邻格子for(int[]dir:DIRECTIONS){area+=dfs(grid,row+dir[0],col+dir[1],islandId);}returnarea;}}

算法分析

时间复杂度：O(n²)
- 每个格子最多被访问一次进行DFS，总时间复杂度 O(n²)
- 遍历所有海洋格子，每个格子检查4个邻居，总时间复杂度 O(n²)
空间复杂度：O(n²)
- 岛屿面积映射表最多存储 O(n²) 个岛屿信息
- DFS递归栈深度最坏情况下为 O(n²)
- Set临时存储最多4个相邻岛屿编号，空间为 O(1)

算法过程

输入：grid = [[1,0],[0,1]]

岛屿识别和标记

格子(0,0)：值为1，开始DFS
- 标记为岛屿2，面积=1
- grid变为：[[2,0],[0,1]]
格子(1,1)：值为1，开始DFS
- 标记为岛屿3，面积=1
- grid变为：[[2,0],[0,3]]
岛屿面积映射：{2: 1, 3: 1}

模拟填海

格子(0,1)：海洋格子
- 上：无，下：grid[1][1]=3，左：grid[0][0]=2，右：无
- 相邻岛屿：{2, 3}
- 总面积：1 + 1 + 1 = 3
格子(1,0)：海洋格子
- 上：grid[0][0]=2，下：无，左：无，右：grid[1][1]=3
- 相邻岛屿：{2, 3}
- 总面积：1 + 1 + 1 = 3

结果

初始最大面积：1
填海后最大面积：3
返回结果：3

测试用例

publicstaticvoidmain(String[]args){Solutionsolution=newSolution();// 测试用例1：对角线岛屿int[][]grid1={{1,0},{0,1}};System.out.println("Test 1: "+solution.largestIsland(grid1));// 3// 测试用例2：三格陆地一格海洋int[][]grid2={{1,1},{1,0}};System.out.println("Test 2: "+solution.largestIsland(grid2));// 4// 测试用例3：全陆地int[][]grid3={{1,1},{1,1}};System.out.println("Test 3: "+solution.largestIsland(grid3));// 4// 测试用例4：全海洋int[][]grid4={{0,0},{0,0}};System.out.println("Test 4: "+solution.largestIsland(grid4));// 1// 测试用例5：复杂情况int[][]grid5={{1,0,1},{0,0,0},{1,0,1}};System.out.println("Test 5: "+solution.largestIsland(grid5));// 5// 测试用例6：单格int[][]grid6={{0}};System.out.println("Test 6: "+solution.largestIsland(grid6));// 1int[][]grid7={{1}};System.out.println("Test 7: "+solution.largestIsland(grid7));// 1// 测试用例8：大岛屿int[][]grid8={{0,0,0,0,0,0,0},{0,1,1,1,1,0,0},{0,1,0,0,1,0,0},{0,1,0,0,1,0,0},{0,1,1,1,1,0,0},{0,0,0,0,0,0,0},{0,0,0,0,0,0,0}};System.out.println("Test 8: "+solution.largestIsland(grid8));// 17}