这是一道经典的深度优先搜索(DFS)问题,可以通过标记岛屿编号 + 面积映射来求解。思路如下:

  1. 遍历整个网格,对每个陆地格子(值为1)进行DFS,给它分配一个唯一的编号(从2开始),并统计该岛屿的面积,存入一个哈希表 area 中。
  2. 再次遍历每个海洋格子(值为0),检查它上下左右四个方向相邻的岛屿编号(去重),将这些岛屿的面积相加,再加上当前格子变为1的面积(即1),得到一个候选面积。记录所有候选面积的最大值。
  3. 特殊情况:如果网格中完全没有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)。

Logo

欢迎加入DeepSeek 技术社区。在这里,你可以找到志同道合的朋友,共同探索AI技术的奥秘。

更多推荐