LeetCode 827. 最大人工岛

2026-09-03 HGNULB 约 12 分钟

文章信息 8 个分类 5 个标签

分类

题目描述

✅ 827. 最大人工岛

题意分析

给一个 $n \times n$ 的 0/1 矩阵，1 表示陆地、0 表示水。允许把至多一个 0 改成 1，问改完之后最大的那座岛（四连通的 1 组成的连通块）能有多大。

「至多一个」这三个字包含两层意思：可以改一个，也可以一个都不改。后者对应网格里本来就没有 0 的情形，这时答案就是 $n^2$；如果只统计「改某个 0 之后」的收益，全是 1 的输入会得到 0，是最典型的漏解。

「四连通」明确了邻接关系只有上下左右，不含对角线，方向数组必须只写四个。

关键的隐含信息是：把某个 0 改成 1 之后，新岛的大小等于「这个格子自身的 1」加上「它四个邻居所属的互不相同的岛的面积之和」。之所以强调互不相同，是因为两个邻居很可能属于同一座岛——比如一个 L 形的岛把某个 0 夹在中间——此时那座岛的面积只能算一次。

规模上 $n \le 500$，格子数是 $2.5 \times 10^5$。这个量级允许对每个格子做常数次操作，但不允许对每个 0 都重新跑一遍连通块搜索：那会是 $O(n^4)$，也就是 $6 \times 10^{10}$，远远超时。

边界要单独想清楚三种输入：全是 1（没有可改的 0）、全是 0（改哪个都只能得到大小为 1 的岛）、以及某个 0 的多个邻居属于同一座岛。

解法：染色 + 枚举翻转

核心思路

暴力做法是照定义演：枚举每一个 0，把它临时改成 1，然后跑一遍完整的连通块搜索求最大岛，再改回去。单次搜索 $O(n^2)$，候选 0 最多 $n^2$ 个，总代价 $O(n^4)$，在 $n = 500$ 时彻底不可行。

瓶颈非常明显：每次翻转之后我们都把整张图重新算了一遍，但实际上绝大部分岛的形状和面积根本没变。翻转只在被改的那个格子周围产生局部影响——它把自己的若干个邻岛粘成一块，其余岛纹丝不动。

于是思路转向：把「与翻转无关的静态信息」预先算好，让每次翻转的收益能在常数时间内查出来。这个静态信息就是「每个陆地格子属于哪座岛」和「每座岛有多大」。

具体做法是给每座岛染一个唯一编号。编号直接写回 grid 本身，省掉一个额外数组；但编号必须从 2 开始，因为 0 和 1 已经被原始语义占用了——如果从 1 开始编号，就再也分不清「这个格子已经染过色」和「这个格子还没处理」。染色用一次深度优先搜索完成，顺手统计每座岛的格子数，存进一张「编号到面积」的表。

染完之后，grid 的语义已经改变，不变量变成：每个原本为 1 的格子现在存着它所属岛的编号（一个不小于 2 的整数），每个原本为 0 的格子仍然是 0；且 area[id] 恒等于编号为 id 的那座岛的真实格子数。

有了这两条，枚举阶段就只剩查表：对每个仍为 0 的格子，看它上下左右四个方向，收集邻居格子上的编号（跳过越界和值为 0 的），用一个集合去重，把去重后各编号对应的面积加起来，再加上被翻转格子自身的 1，就是把这个 0 改成 1 之后新岛的大小。

最后还要把「一个都不改」这条路也纳入比较：先用所有岛的面积最大值给答案打底，再让每个候选翻转去刷新它。这样全是 1 的输入自然得到 $n^2$，不需要任何特判。

解题步骤

第一轮扫描全图，遇到值恰好为 1 的格子就以它为起点做一次深度优先搜索，把整座岛的格子都改写成当前编号 id，并返回这座岛的面积记进表里，随后 id 自增。为什么起始编号取 2：0 表示水、1 表示「尚未染色的陆地」，编号必须避开这两个值，否则递归会分不清该不该继续。

深度优先搜索的终止条件写成「越界，或者格子的值不等于 1」。为什么是「不等于 1」而不是「等于 0」：已经染过色的格子值大于等于 2，用「等于 0」判断会让它们被反复递归，直接死循环。

用所有岛的面积最大值初始化答案。为什么这一步不能省：它覆盖了「一个 0 都没有、无需翻转」的情形；跳过它的话，全 1 的输入会得到 0。

第二轮扫描全图，只处理值仍为 0 的格子。对每个这样的格子，准备一个空集合和一个初值为 1 的累加器。为什么累加器从 1 起：被翻转的格子自己也变成了陆地，要算进新岛。

依次查看四个方向的邻居，越界的跳过，值不大于 1 的跳过（也就是水），剩下的编号尝试放进集合；只有放进去成功（说明这个编号是第一次见）才把对应面积累加。为什么必须去重：一座 L 形或 U 形的岛可能从两个甚至三个方向包住同一个 0，不去重会把它的面积重复计入。

用累加结果刷新答案，扫完返回。

以 grid = [[1,0],[0,1]] 走一遍：第一轮，$(0,0)$ 的值为 1，以 id = 2 染色，这座岛只有它自己，area[2] = 1，grid 变成 [[2,0],[0,1]]，id 变为 3。继续扫到 $(1,1)$ 值为 1，以 id = 3 染色，area[3] = 1，grid 变成 [[2,0],[0,3]]，id 变为 4。答案先被岛面积最大值打底为 1。

第二轮，$(0,1)$ 的值为 0：向上越界跳过；向下是 $(1,1)$，值为 3，集合里没有，加入并累加，累加器从 1 变成 2；向左是 $(0,0)$，值为 2，集合里没有，加入并累加，累加器变成 3；向右越界跳过。答案刷新为 3。再看 $(1,0)$：向上是 $(0,0)$ 编号 2，累加器变成 2；向下越界；向左越界；向右是 $(1,1)$ 编号 3，累加器变成 3。答案仍是 3。返回 $3$，对应把任意一个 0 改成 1 后两座单格岛被连成一条长度为 3 的岛。

再看一个需要去重的例子 grid = [[1,1],[1,0]]：第一轮把左上三个格子染成同一座岛，area[2] = 3，答案打底为 3。第二轮处理 $(1,1)$：向上是 $(0,1)$ 编号 2，累加器从 1 变成 4；向左是 $(1,0)$ 编号同样是 2，集合里已经有了，跳过不再累加。答案是 4，正确。如果漏掉去重，这里会算成 $1 + 3 + 3 = 7$。

代码末尾那句「答案为 0 就返回 $n^2$」在本题约束下其实触发不到：$n \ge 1$ 时，要么存在陆地使打底值至少为 1，要么全是水使某个 0 的翻转结果至少为 1。它是一层防御性兜底，保留无害。

代码实现

// 对每个 0 格子，查看四邻的岛屿编号，累加不同岛屿的面积再加 1。
class Solution {
    private int n;
    private int[][] grid;
    private int id = 2;

    public int largestIsland(int[][] grid) {
        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 = dfs(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);
            }
        }

        if (best == 0) {
            return n * n;
        }
        return best;
    }

    private int dfs(int r, int c, int idx) {
        if (r < 0 || r >= n || c < 0 || c >= n || grid[r][c] != 1) {
            return 0;
        }

        grid[r][c] = idx;
        int res = 1;
        res += dfs(r - 1, c, idx);
        res += dfs(r + 1, c, idx);
        res += dfs(r, c - 1, idx);
        res += dfs(r, c + 1, idx);
        return res;
    }
}

// 对每个 0 格子，查看四邻的岛屿编号，累加不同岛屿的面积再加 1。
func largestIsland(grid [][]int) int {
    n := len(grid)
    id := 2
    area := make(map[int]int)

    var dfs func(r int, c int, idx int) int
    dfs = func(r int, c int, idx int) int {
        if r < 0 || r >= n || c < 0 || c >= n || grid[r][c] != 1 {
            return 0
        }
        grid[r][c] = idx
        res := 1
        res += dfs(r-1, c, idx)
        res += dfs(r+1, c, idx)
        res += dfs(r, c-1, idx)
        res += dfs(r, c+1, idx)
        return res
    }

    for i := 0; i < n; i++ {
        for j := 0; j < n; j++ {
            if grid[i][j] == 1 {
                a := dfs(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
            }
        }
    }

    if best == 0 {
        return n * n
    }
    return best
}

复杂度分析

时间复杂度：$O(n^2)$，其中 $n$ 是网格边长。染色阶段每个格子最多被递归进入常数次（进入后立刻被改写成编号，不会再次满足「值为 1」的条件），总代价与格子数同阶；枚举阶段每个 0 格子只看四个固定方向，集合最多装 4 个元素，单格是常数级。两个阶段相加仍是格子数的线性倍。

空间复杂度：$O(n^2)$。面积表最坏情况下有约 $n^2/2$ 项（棋盘格状分布时岛的数量达到上限）；深度优先搜索的递归栈在蛇形长岛上可达 $O(n^2)$ 层；编号直接写回 grid 不额外占空间。

关键点总结

「枚举一次修改、求修改后的最优值」这类题的通用套路是：先把与修改无关的静态结构预处理好，再让每个候选修改只做常数级查询。判断能不能这么做的依据是「一次修改的影响是否局部」——本题的翻转只会粘合它的四个邻岛，其余部分完全不动。

把连通块编号直接写回原网格是很实用的技巧，省掉一个同尺寸数组。前提是编号要避开原有取值，所以从 2 开始；对应地，搜索的终止条件必须写成「值不等于 1」而不是「值等于 0」。

邻居去重是本题唯一的算法性陷阱。同一座岛可以从多个方向贴着同一个 0，不去重会把它的面积重复计入。只用四个方向、集合最多四个元素，所以去重的开销可以忽略。

「至多一次操作」必须包含「零次操作」这条分支。用所有岛的最大面积给答案打底，是把它并入主流程最干净的写法，比在末尾特判全 1 更不容易漏。

面试视角：并查集是完全等价的替代方案——建图时把相邻的 1 合并，用带大小的并查集，枚举时收集四个邻居的根节点去重。两种写法都要能说出来；如果面试官强调 $n = 500$ 时深度优先搜索可能递归两万五千层导致栈溢出，并查集或改成广度优先搜索就是标准应对。

易错点总结

错误写法：累加邻居面积时不做去重。用例 grid = [[1,1],[1,0]] 中 $(1,1)$ 的上邻和左邻同属编号 2 的那座岛，不去重会算成 $1 + 3 + 3 = 7$，正确答案是 4。

错误写法：岛的编号从 1 开始。染完色的格子值仍是 1，外层扫描会把它当成「还没处理的陆地」再染一次，同一座岛被切成若干块，面积表全错。

错误写法：深度优先搜索的终止条件写成 grid[r][c] == 0 才返回。值为 2 及以上的已染色格子不满足这个条件，会被无限递归下去直到栈溢出。

错误写法：只统计翻转每个 0 的收益，不用岛面积最大值打底。用例 grid = [[1,1],[1,1]] 里一个 0 都没有，第二轮循环一次也不执行，答案会是 0 而不是 4。

错误写法：累加器从 0 开始而不是 1。被翻转的格子自身没被算进去，用例 grid = [[0,0],[0,0]] 的正确答案是 1，这么写会返回 0。

错误写法：枚举阶段判断邻居是否为陆地时写成 grid[ni][nj] == 1。染色之后网格里已经没有值为 1 的格子，这个条件恒不成立，所有翻转的收益都会退化成 1。

错误写法：方向数组写了八个方向。题目定义的是四连通，对角相邻的两座岛并不会因为中间那个 0 被翻转而连通，用例 grid = [[1,0],[0,1]] 会被算成把两座岛都接上，虽然本例答案巧合正确，但在更大的斜向布局上会严重偏大。

错误写法：先枚举 0 格子再做染色。枚举阶段读到的还是原始的 0/1，根本没有编号可查，逻辑无法成立。

错误写法：面积表用定长数组存却按岛的数量估算大小。棋盘格状的输入里岛的数量能达到约 $n^2/2$，编号会一直涨到那个量级，数组开小了必然越界；用哈希表则不必操心上界。

相似题目

题目	难度	考察点
200. 岛屿数量	中等	只需数出连通块个数，遍历一遍标记已访问即可，不需要给岛编号也不需要记录面积
695. 岛屿的最大面积	中等	恰好是本题染色阶段的独立版本，求的是原图中最大岛的面积，没有「翻转一格」这一层枚举
305. 岛屿数量 II	困难	陆地是逐个动态加入的，必须用带路径压缩的并查集在线维护连通块数量，深度优先搜索的静态染色思路在这里失效