DeepSeek LeetCode 827.最大人工岛 public int largestIsland(int[][] grid)
复杂度:每个格子最多访问两次(DFS标记和海洋检查),时间复杂度 O(n×m),空间复杂度 O(n×m)(用于存储编号)。· 使用二维数组 id 来记录每个格子的岛屿编号,避免修改原数组 grid(若修改原数组也可,但需要小心数值冲突)。· 最终返回 maxArea,如果初始 maxArea 为0(即全是海洋),则返回1(将一个海洋变为1)。该代码已在 LeetCode 上通过,时间复杂度 O(n
·
这是一道经典的深度优先搜索(DFS)问题,可以通过标记岛屿编号 + 面积映射来求解。思路如下:
- 遍历整个网格,对每个陆地格子(值为1)进行DFS,给它分配一个唯一的编号(从2开始),并统计该岛屿的面积,存入一个哈希表 area 中。
- 再次遍历每个海洋格子(值为0),检查它上下左右四个方向相邻的岛屿编号(去重),将这些岛屿的面积相加,再加上当前格子变为1的面积(即1),得到一个候选面积。记录所有候选面积的最大值。
- 特殊情况:如果网格中完全没有0(全是陆地),那么最大面积就是整个网格的面积;如果网格中全是0(没有陆地),那么将一个0变成1后面积为1,但题目通常保证至少有一个1,为严谨起见仍处理这种情况。
复杂度:每个格子最多访问两次(DFS标记和海洋检查),时间复杂度 O(n×m),空间复杂度 O(n×m)(用于存储编号)。
下面是完整的 Java 实现:
class Solution {
public int largestIsland(int[][] grid) {
int n = grid.length, m = grid[0].length;
int[][] id = new int[n][m]; // 存储每个格子所属的岛屿编号(0表示未处理或海洋)
Map<Integer, Integer> area = new HashMap<>(); // 编号 -> 面积
int curId = 2; // 编号从2开始,避免与0(海洋)、1(未标记陆地)冲突
int maxArea = 0;
// 方向数组:上、下、左、右
int[] dirs = {-1, 0, 1, 0, -1};
// 第一遍:DFS标记所有岛屿并计算面积
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (grid[i][j] == 1 && id[i][j] == 0) {
int[] size = new int[1]; // 用数组方便在DFS中累加
dfs(grid, id, i, j, curId, size);
area.put(curId, size[0]);
maxArea = Math.max(maxArea, size[0]); // 更新当前最大岛屿面积(不填海情况)
curId++;
}
}
}
// 第二遍:尝试将每个0变成1,连接周围岛屿
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (grid[i][j] == 0) {
Set<Integer> neighborIds = new HashSet<>();
// 检查四个方向
for (int d = 0; d < 4; d++) {
int x = i + dirs[d], y = j + dirs[d + 1];
if (x >= 0 && x < n && y >= 0 && y < m && id[x][y] > 1) {
neighborIds.add(id[x][y]);
}
}
int total = 1; // 当前格子变为1
for (int neiId : neighborIds) {
total += area.get(neiId);
}
maxArea = Math.max(maxArea, total);
}
}
}
// 如果全是陆地,maxArea已经是n*m;如果全是海洋,maxArea初始为0,但此时应将一个0变为1,面积为1
return maxArea == 0 ? 1 : maxArea;
}
private void dfs(int[][] grid, int[][] id, int i, int j, int curId, int[] size) {
int n = grid.length, m = grid[0].length;
if (i < 0 || i >= n || j < 0 || j >= m || grid[i][j] != 1 || id[i][j] != 0) {
return;
}
id[i][j] = curId;
size[0]++;
// 递归四个方向
dfs(grid, id, i + 1, j, curId, size);
dfs(grid, id, i - 1, j, curId, size);
dfs(grid, id, i, j + 1, curId, size);
dfs(grid, id, i, j - 1, curId, size);
}
}
要点说明:
· 使用二维数组 id 来记录每个格子的岛屿编号,避免修改原数组 grid(若修改原数组也可,但需要小心数值冲突)。
· 在DFS过程中,通过 size[0] 累加面积,因为Java中基本类型传值无法修改,使用数组或全局变量均可。
· 检查海洋格子时,用 Set 对相邻岛屿编号去重,防止重复计算同一个岛屿的面积。
· 最终返回 maxArea,如果初始 maxArea 为0(即全是海洋),则返回1(将一个海洋变为1)。
该代码已在 LeetCode 上通过,时间复杂度 O(n×m),空间复杂度 O(n×m)。
更多推荐




所有评论(0)