LeetCode 305. 岛屿数量 II

2021-10-20 HGNULB 约 13 分钟

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

分类

题目描述

✅ 305. 岛屿数量 II

题意分析

给一个初始全是水的 m×n 网格，以及一串操作，每次把某个位置变成陆地。每次操作之后都要报告当前的岛屿数量，最终返回一个与操作序列等长的答案数组。岛屿的定义仍是四连通的陆地连通块。

与静态的岛屿计数最大的区别是「在线」：结果要随着每次操作实时给出，不能等所有陆地都加完再统计。这条约束否决了「每次操作后重新跑一遍 DFS」的做法——那是 $O(k \cdot m \cdot n)$，操作数上万时必然超时。

数据的演化方向是单向的：只加陆地、不删陆地。这是一条极其关键的信号。连通块只会合并、不会分裂，正是并查集擅长的场景（并查集不支持删边，一旦有删除操作就要换成别的结构）。

岛屿数量的变化也因此非常规律：新增一块陆地先让计数加一，随后它每与一个此前不连通的邻居岛屿合并一次，计数就减一。

边界包括：同一个位置可能被重复添加，第二次起不应改变任何计数；新陆地可能同时挨着两个原本属于同一个岛的格子，此时只能算一次合并；网格边缘的邻居要做越界判断。

解法：并查集动态合并陆地

核心思路

先看为什么暴力不行。每加一块陆地就对整个网格重跑一次洪水填充，单次 $O(mn)$，操作数 k 次就是 $O(k \cdot mn)$。但仔细想会发现，一次操作只影响新格子周围最多四个方向的连通关系，重扫全图的工作绝大部分是白做的。

目标因此变成：只用局部信息就把全局的岛屿数量更新对。观察岛屿数量的变化规律——加入一块新陆地时，它自己先算作一个独立的岛，计数加一；然后依次考察四个邻居，若邻居是陆地且与新格子当前尚未连通，就把两者合并，两个岛变成一个，计数减一。若邻居虽是陆地但早已通过别的路径与新格子连通，则不能再减。

「判断两个格子是否已连通」和「把两个连通块合并」正是并查集的两个基本操作，而且都近似常数时间。为了用一维的并查集表示二维网格，把坐标 (row, col) 映射成编号 row * n + col——这个映射是双射，且只依赖列数 n，是网格类并查集的标准写法。

还需要一个 active 标记数组，区分「这个格子已经是陆地」和「还是水」。并查集的 parent 数组初始时每个格子都自成一个集合，但那时它们还都是水，不能算作岛；active 让我们只对真正的陆地做合并与计数。

由此得到的不变量是：每次操作处理完毕时，count 恰好等于当前所有 active 格子构成的四连通块个数。加一表示新格子暂时自成一岛，每次成功合并减一表示两个块并成了一个，而 union 返回布尔值正是为了区分「真的合并了」与「本来就同属一块」——只有前者才减。

重复添加的处理也很自然：若该位置已经 active，说明网格没有任何变化，直接把当前 count 追加进答案并跳过后续逻辑。漏掉这个判断会让 count 凭空多一。

解题步骤

初始化容量为 m * n 的并查集，parent 指向自身、rank 全 0、active 全 false；准备方向数组、岛屿计数 count 和答案列表。并查集一次性开满整个网格，避免动态扩容。

逐个处理操作位置，先把 (row, col) 换算成编号 row * n + col。乘的是列数 n，因为一行有 n 个格子，写成 row * m + col 是最常见的低级错误。

若该编号已经 active，说明这块陆地此前已经加过，网格状态不变，直接把当前 count 记入答案并处理下一个操作。

否则把它标成 active 并让 count 加一，先假设它是一座新的独立岛屿。这个「先加后减」的顺序让后面的合并逻辑变得统一。

枚举四个方向的邻居，先做越界判断再取编号。越界判断必须在计算编号之前，否则越界坐标算出的编号可能恰好落在数组范围内（比如 col = -1 时会绕到上一行的末尾），造成看似合法实则错误的连通。

若邻居 active 且 union 返回 true（说明此前不连通，本次真的合并了），count 减一。用返回值判断而不是先 find 再比较，是把两步合成一步，也避免了忘记判重。

每次操作结束把 count 追加进答案。

以 m = 3、n = 3、positions = [[0,0],[0,1],[1,2],[2,1]] 走一遍，期望输出 [1,1,2,3]。

第一次加 (0,0)，编号 0。未 active，标记后 count 变成 1。四个邻居中 (-1,0) 与 (0,-1) 越界跳过，(1,0) 编号 3 和 (0,1) 编号 1 都还是水，不合并。答案记 1。

第二次加 (0,1)，编号 1。未 active，count 变成 2。邻居 (1,1) 编号 4 是水；(0,2) 编号 2 是水；(0,0) 编号 0 是陆地，union(1, 0) 发现两者根不同，合并成功返回 true，count 减回 1。答案记 1——两块相邻的陆地合成了一座岛。

第三次加 (1,2)，编号 5。未 active，count 变成 2。邻居 (2,2) 编号 8 是水，(0,2) 编号 2 是水，(1,3) 越界，(1,1) 编号 4 是水，没有任何合并。答案记 2——右侧多出一座孤岛。

第四次加 (2,1)，编号 7。未 active，count 变成 3。邻居 (3,1) 越界，(1,1) 编号 4 是水，(2,2) 编号 8 是水，(2,0) 编号 6 是水，同样无合并。答案记 3。

最终返回 [1,1,2,3]。

值得单独体会第二步：如果 union 不返回布尔值而是无条件让 count 减一，那么当一块新陆地同时挨着两个已经属于同一岛的格子时（例如在 [[0,0],[0,1],[1,0],[1,1]] 这样的操作序列末尾加 (1,1)，它的上邻和左邻早已连通），count 会被多减一次，答案偏小。

代码实现

class Solution {
    public List<Integer> numIslands2(int m, int n, int[][] positions) {
        UnionFind uf = new UnionFind(m * n);
        int[][] dirs = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
        List<Integer> res = new ArrayList<>();
        int count = 0;

        for (int[] pos : positions) {
            int row = pos[0];
            int col = pos[1];
            int id = row * n + col;
            if (uf.active[id]) {
                res.add(count);
                continue;
            }

            uf.active[id] = true;
            count++;

            for (int[] dir : dirs) {
                int nextRow = row + dir[0];
                int nextCol = col + dir[1];
                if (nextRow < 0 || nextRow >= m || nextCol < 0 || nextCol >= n) {
                    continue;
                }

                int nextId = nextRow * n + nextCol;
                if (uf.active[nextId] && uf.union(id, nextId)) {
                    count--;
                }
            }

            res.add(count);
        }

        return res;
    }

    static class UnionFind {
        int[] parent;
        int[] rank;
        boolean[] active;

        UnionFind(int size) {
            parent = new int[size];
            rank = new int[size];
            active = new boolean[size];
            for (int i = 0; i < size; i++) {
                parent[i] = i;
            }
        }

        int find(int x) {
            if (parent[x] != x) {
                parent[x] = find(parent[x]);
            }
            return parent[x];
        }

        boolean union(int x, int y) {
            int rootX = find(x);
            int rootY = find(y);
            if (rootX == rootY) {
                return false;
            }

            if (rank[rootX] < rank[rootY]) {
                parent[rootX] = rootY;
            } else if (rank[rootX] > rank[rootY]) {
                parent[rootY] = rootX;
            } else {
                parent[rootY] = rootX;
                rank[rootX]++;
            }
            return true;
        }
    }
}

func numIslands2(m int, n int, positions [][]int) []int {
    uf := newUnionFind(m * n)
    dirs := [][2]int{{1, 0}, {-1, 0}, {0, 1}, {0, -1}}
    res := make([]int, 0, len(positions))
    count := 0

    for _, pos := range positions {
        row, col := pos[0], pos[1]
        id := row*n + col
        if uf.active[id] {
            res = append(res, count)
            continue
        }

        uf.active[id] = true
        count++

        for _, dir := range dirs {
            nextRow := row + dir[0]
            nextCol := col + dir[1]
            if nextRow < 0 || nextRow >= m || nextCol < 0 || nextCol >= n {
                continue
            }

            nextId := nextRow*n + nextCol
            if uf.active[nextId] && uf.union(id, nextId) {
                count--
            }
        }

        res = append(res, count)
    }

    return res
}

type unionFind struct {
    parent []int
    rank   []int
    active []bool
}

func newUnionFind(size int) *unionFind {
    parent := make([]int, size)
    rank := make([]int, size)
    active := make([]bool, size)
    for i := 0; i < size; i++ {
        parent[i] = i
    }
    return &unionFind{parent: parent, rank: rank, active: active}
}

func (uf *unionFind) find(x int) int {
    if uf.parent[x] != x {
        uf.parent[x] = uf.find(uf.parent[x])
    }
    return uf.parent[x]
}

func (uf *unionFind) union(x int, y int) bool {
    rootX := uf.find(x)
    rootY := uf.find(y)
    if rootX == rootY {
        return false
    }

    if uf.rank[rootX] < uf.rank[rootY] {
        uf.parent[rootX] = rootY
    } else if uf.rank[rootX] > uf.rank[rootY] {
        uf.parent[rootY] = rootX
    } else {
        uf.parent[rootY] = rootX
        uf.rank[rootX]++
    }
    return true
}

复杂度分析

时间复杂度：$O(mn + k \cdot \alpha(mn))$，其中 k 是操作数，$\alpha$ 是反阿克曼函数。初始化并查集是 $O(mn)$；每次操作只做常数次（至多四次）合并，路径压缩加按秩合并让单次操作近似常数。

空间复杂度：$O(mn)$，parent、rank、active 三个数组都与网格格子数同阶；答案列表额外占 $O(k)$。

关键点总结

「动态加边、实时查询连通块个数」是并查集的招牌场景；反过来，一旦题目出现删除操作，并查集就不再适用，要考虑离线倒序处理或改用别的结构。

连通块计数的通用维护方式是「新增元素先加一，每次成功合并减一」，其中「成功」二字必须由 union 的返回值判定，无条件减一会在多个邻居同属一块时算错。

二维网格转一维编号统一写成 row * 列数 + col，乘的永远是列数；这个约定要固定下来，混用行数是这类题最高频的低级错误。

越界判断必须在计算编号之前完成，因为负下标或超界坐标算出的编号可能仍落在数组范围内，会造成跨行的虚假连通。

并查集本身要写全两个优化：find 里的路径压缩和 union 里的按秩（或按大小）合并，缺一个都可能在极端数据上退化成链。

面试视角：面试官通常先让你说清「为什么不能每次重跑 DFS」，再让你手写并查集模板（这道题的真正考点就是能否白板默写出带两种优化的并查集）。追问点常有三个——重复添加怎么处理、一次操作最多减几次、如果要支持删除陆地该怎么办（答案是离线倒序，把删除变成添加）。

易错点总结

错误写法：编号写成 row * m + col → 用例 m = 1, n = 3, positions = [[0,2]]，编号算成 2 碰巧正确，但 m = 3, n = 1, positions = [[2,0]] 会算成 6 而数组长度只有 3，直接越界异常。

错误写法：漏掉「该位置已是陆地」的判断 → 用例 m = 1, n = 1, positions = [[0,0],[0,0]]，第二次重复添加又让 count 加一，返回 [1,2]，正确答案是 [1,1]。

错误写法：合并时无条件 count-- 而不看 union 的返回值 → 用例 m = 2, n = 2, positions = [[0,0],[0,1],[1,0],[1,1]]，最后加入的 (1,1) 有两个邻居且它们早已连通，count 被多减一次，返回末位 0，正确答案是 1。

错误写法：先算 nextId 再做越界判断 → 用例 m = 2, n = 2, positions = [[1,0]]，左邻 (1,-1) 算出编号 1，恰好落在数组内，会与实际不相邻的格子建立虚假连通。

错误写法：忘记检查邻居是否 active，对所有相邻编号都做 union → 用例 m = 2, n = 2, positions = [[0,0]]，把还是水的格子并了进来，之后这些水格变成陆地时不再触发合并，count 全程偏小。

错误写法：并查集初始化时忘记 parent[i] = i → 用例任意，所有节点的根都是 0，第一次 union 就返回 false，count 只增不减，答案全部偏大。

错误写法：find 不做路径压缩 → 用例是长链式的添加顺序（如一整列自上而下逐格添加），树高退化成 $O(mn)$，每次查询都要走满一条链，在大网格上超时。

错误写法：union 里直接 parent[x] = y 而不是操作两者的根 → 用例 positions = [[0,0],[0,1],[0,2]]，已有的连通信息被覆盖，之前并进来的成员被割裂出去，count 出错。

错误写法：按秩合并时更新了错误的 rank，例如在 rank[rootX] < rank[rootY] 分支里也执行 rank[rootX]++ → 秩失去意义，树可能退化，虽然结果仍对但性能不再有保证。

错误写法：active 标记在合并之后才置位 → 用例 m = 1, n = 2, positions = [[0,0],[0,1]]，处理 (0,1) 时它自己还不是 active，若合并逻辑里也检查了自身的 active 就会跳过合并，返回 [1,2]，正确答案是 [1,1]。

错误写法：答案在重复添加的分支里忘记 res.add(count) 就 continue → 用例 positions = [[0,0],[0,0]]，返回的数组只有一个元素，长度与操作数不符，直接判错。

错误写法：每次操作后重新跑一遍 DFS 统计岛屿 → 用例是 $10^4$ 次操作的大网格，单次 $O(mn)$ 累积成上亿次访问，超时。

相似题目

题目	难度	考察点
200. 岛屿数量	中等	静态一次性统计，用洪水填充比并查集更直接
547. 省份数量	中等	输入是邻接矩阵，合并对象是节点而非网格坐标
130. 被围绕的区域	中等	需要引入一个虚拟节点代表边界，把「是否连到外部」并进来
684. 冗余连接	中等	靠 union 返回 false 来定位第一条成环的边
721. 账户合并	中等	元素是字符串，需要额外的映射把邮箱编号化并在最后归组排序
990. 等式方程的可满足性	中等	要分两趟处理，先合并所有等式再逐条校验不等式
128. 最长连续序列	中等	并查集需同时维护集合大小，也可用哈希集合做线性扫描
1319. 连通网络的操作次数	中等	答案由连通块数减一给出，还要先判断线缆是否够用
839. 相似字符串组	困难	边由两两比较隐式生成，建图本身就是 $O(n^2 \cdot len)$