LeetCode 827. 最大人工岛

约 10 分钟
文章信息 8 个分类 5 个标签
分类
LeetCode CodeTop 困难 未解决 2-5 字节 微软 猿辅导
标签
数组 深度优先搜索 广度优先搜索 矩阵 并查集

题目描述

✅ 827. 最大人工岛

image-20260928225105166

image-20260928225105176

题意分析

最多把一个 0 改成 1，求修改后最大的四连通岛屿面积。只能上下左右相连，对角线相邻不算连通；也可以不修改任何格子。

如果对每个水格都重新搜索整张图，会重复计算原有岛屿。一次翻转只会把这个格子与四周接触到的岛连接起来，因此可以先统计所有原有岛屿，再直接计算每个翻转位置的收益。

解法：染色 + 枚举翻转

核心思路

[!blue]

第一遍扫描把每座岛染成独立编号，并在 area[id] 中保存面积。编号从 2 开始，避免与原来的水格 0、尚未处理的陆地 1 混淆。染色使用显式栈，每发现一个 1 就先写入编号再入栈，因此同一格不会被多个方向重复发现，出栈时只计入面积一次。

第二遍枚举每个水格。若把它翻成陆地，新岛面积就是“当前格子的 1，加上四邻中所有不同岛屿的面积”。必须按岛屿编号去重，因为四个相邻陆地格可能本来就属于同一座岛，不能重复加上整座岛的面积。

这个面积恰好覆盖翻转后的整个连通块：与新格相邻的岛都会通过它连接，而不相邻的岛若仍被水隔开，就不可能只靠这一次翻转接入。对所有水格计算一次，再与原有最大岛面积比较，就覆盖了所有可选方案。

先用原有岛屿面积初始化 best，也包含“不翻转”的情况。全陆地时没有水格可枚举，直接保留 n*n；全水时没有邻岛，每个候选面积都是 1。题目保证网格非空，这两种情况都不需要额外兜底。

解题步骤

  1. 从编号 2 开始扫描网格。遇到尚未染色的 1，用栈遍历整座岛，写入统一编号并记录面积，之后增加编号。
  2. 从面积表中取得原有最大岛面积，作为 best 的初值。
  3. 再次扫描每个 0，把候选面积 sum 初始化为 1，并创建当前候选专用的编号集合 seen。
  4. 检查四个相邻位置，跳过越界、水格和已经统计的岛编号，把首次遇到的邻岛面积加入 sum。
  5. 用 sum 更新 best，枚举结束后返回 best。染色直接写回网格，因此会修改输入。

代码实现

class Solution {
    private int n;
    private int[][] grid;
    private int id = 2;

    public int largestIsland(int[][] grid) {
        id = 2;
        this.n = grid.length;
        this.grid = grid;
        Map<Integer, Integer> area = new HashMap<>();

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == 1) {
                    int a = paint(i, j, id);

                    area.put(id, a);
                    id++;
                }
            }
        }

        int best = 0;

        for (int val : area.values()) {
            best = Math.max(best, val);
        }

        int[] dr = {
            -1,
            1,
            0,
            0
        };
        int[] dc = {
            0,
            0,
            -1,
            1
        };

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] != 0) {
                    continue;
                }

                Set<Integer> seen = new HashSet<>();
                // 翻转的这个海水格自身贡献一
                int sum = 1;

                for (int k = 0; k < 4; k++) {
                    int ni = i + dr[k];
                    int nj = j + dc[k];

                    if (ni < 0 || ni >= n || nj < 0 || nj >= n) {
                        continue;
                    }

                    int idx = grid[ni][nj];

                    // 同一座岛可能从多方向相邻，面积只能累加一次
                    if (idx > 1 && seen.add(idx)) {
                        sum += area.get(idx);
                    }
                }

                best = Math.max(best, sum);
            }
        }

        return best;
    }

    private int paint(int r, int c, int idx) {
        Deque<int[]> stack = new ArrayDeque<>();

        grid[r][c] = idx;
        stack.push(new int[] {
            r,
            c
        });
        // 每次弹出一个已编号格，面积只增加一次
        int res = 0;
        int[] dr = {
            -1,
            1,
            0,
            0
        };
        int[] dc = {
            0,
            0,
            -1,
            1
        };

        while (!stack.isEmpty()) {
            int[] cell = stack.pop();

            res++;

            for (int k = 0; k < 4; k++) {
                int nr = cell[0] + dr[k];
                int nc = cell[1] + dc[k];

                if (nr < 0 || nr >= n || nc < 0 || nc >= n || grid[nr][nc] != 1) {
                    continue;
                }

                // 入栈前写编号，防止多个相邻格重复加入
                grid[nr][nc] = idx;
                stack.push(new int[] {
                    nr,
                    nc
                });
            }
        }

        return res;
    }
}

func largestIsland(grid [][]int) int {
    n := len(grid)
    id := 2
    area := make(map[int]int)

    paint := func(r int, c int, idx int) int {
        grid[r][c] = idx
        stack := [][2]int{
            {r, c},
        }
        // 每次弹出一个已编号格，面积只增加一次
        res := 0
        dirs := [][2]int{
            {-1, 0},
            {1, 0},
            {0, -1},
            {0, 1},
        }
        for len(stack) > 0 {
            cell := stack[len(stack)-1]
            stack = stack[:len(stack)-1]
            res++
            for _, d := range dirs {
                nr, nc := cell[0]+d[0], cell[1]+d[1]
                if nr < 0 || nr >= n || nc < 0 || nc >= n || grid[nr][nc] != 1 {
                    continue
                }
                // 入栈前写编号，防止多个相邻格重复加入
                grid[nr][nc] = idx
                stack = append(stack, [2]int{
                    nr,
                    nc,
                })
            }
        }
        return res
    }

    for i := 0; i < n; i++ {
        for j := 0; j < n; j++ {
            if grid[i][j] == 1 {
                a := paint(i, j, id)
                area[id] = a
                id++
            }
        }
    }

    best := 0
    for _, v := range area {
        if v > best {
            best = v
        }
    }

    dirs := make([][2]int, 0, 4)
    dirs = append(
        dirs,
        [2]int{
            -1,
            0,
        },
        [2]int{
            1,
            0,
        },
        [2]int{
            0,
            -1,
        },
        [2]int{
            0,
            1,
        },
    )
    for i := 0; i < n; i++ {
        for j := 0; j < n; j++ {
            if grid[i][j] != 0 {
                continue
            }

            seen := make(map[int]bool)
            // 翻转的这个海水格自身贡献一
            sum := 1
            for _, d := range dirs {
                ni := i + d[0]
                nj := j + d[1]
                if ni < 0 || ni >= n || nj < 0 || nj >= n {
                    continue
                }
                idx := grid[ni][nj]
                // 同一座岛可能从多方向相邻，面积只能累加一次
                if idx > 1 && !seen[idx] {
                    seen[idx] = true
                    sum += area[idx]
                }
            }

            if sum > best {
                best = sum
            }
        }
    }

    return best
}

复杂度分析

  • 时间复杂度：$O(n^2)$。染色时每个陆地格只处理一次；枚举水格时，每个候选只检查四个方向。
  • 空间复杂度：$O(n^2)$，用于显式栈和岛屿面积表。每个候选的去重集合最多包含四个岛编号，占常数空间。

关键点总结

[!green]

  • 先把原有连通块压缩为“编号和面积”，后续候选只需查询四个邻居。
  • 翻转增加一格，并连接所有不同的相邻岛；去重的对象是岛编号。
  • 保留原有最大岛面积，才能自然处理没有水格可翻转的情况。

易错点总结

[!yellow]

  • 相邻岛不去重：同一座岛可能从多个方向接触候选格，但它的面积只能加一次。
  • 染色后仍只识别值为 1 的邻居：已有岛已经变成不小于 2 的编号，应通过编号查询面积。
  • 多个翻转候选共用同一个 seen：去重只针对当前候选，每换一个水格都要重新统计邻岛。
  • 只统计翻转后的候选面积：全陆地时没有候选，会漏掉原有最大岛。
  • 出栈时才写编号：同一格可能被多个邻居重复压栈并重复计数，应在入栈前完成标记。

相似题目

题目 难度 关联与区别
695. 岛屿的最大面积 中等 先标记每个已有岛屿及面积，再比较一次翻0能合并的不同邻接分量。
305. 岛屿数量 II 困难 同样新增陆地后合并相邻分量，本题只选择一次最优新增，原题按给定顺序持续增加。
转载与许可
作者
链接 https://hgnulb.github.io/blog/2026/39754511
许可 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！