LeetCode 305. 岛屿数量 II
题目描述
题意分析
一个
m × n的网格初始全是水，按顺序把指定位置变成陆地，每次操作后都要返回当前岛屿数量。岛屿只按上下左右四个方向连接，对角接触不算连通。操作只会增加陆地，不会拆开已有岛屿，因此可以持续维护连通块。重复添加已经是陆地的格子不改变岛数，但仍要为这次操作输出一个答案。
解法：并查集动态合并陆地
核心思路
[!blue]
用并查集表示陆地所属的岛屿，把坐标
(row, col)映射成一维编号row * n + col。parent保存集合关系，find找到代表整个岛的根；active单独记录这个位置是否已经从水变成陆地。新格子出现时，先把它当作一个独立岛，岛数加一。随后检查四周已经激活的陆地：若新格子所在集合与邻居集合的根不同，就合并两个岛，岛数减一；若根已经相同，说明本来就在同一岛内，不需要再减。
只在合并成功时减一很关键。新格子可能同时接触同一座岛的多个位置，第一个邻居已经把这座岛合并进来，后续邻居不能再次扣除。因此最终变化是“新增一个岛，再减去实际连接到的不同旧岛数量”。
rank记录树高的上界，合并时把秩较小的根挂到较大的根下；两者相同则任选一个根，并将它的秩加一。find找到根后，把查找途中的节点直接连接到根，缩短后续查找路径。这些操作只改变集合的表示，不改变连通关系。虽然代码预先为全部网格位置建立父节点，但未激活的水格始终不计入岛数，也不能参与合并。
解题步骤
- 建立大小为
m * n的并查集和全为假的激活表，岛数初始化为0。- 对每次添加计算编号。如果该位置已激活，直接追加当前岛数，继续下一次操作。
- 将新位置激活，岛数加一；此前水格没有参与合并，所以它仍是独立集合。
- 检查四个邻居，跳过越界位置和水格。对有效陆地调用
union，仅当返回成功时将岛数减一。- 四个方向处理完后记录当前岛数，最终返回每次操作对应的结果列表。
代码实现
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
}
复杂度分析
设添加操作数为
q。
- 时间复杂度：$O(mn+q\alpha(mn))$，初始化全部父节点需要 $O(mn)$；每次操作检查固定四个邻居，并查集合并的均摊开销为反阿克曼函数量级。
- 空间复杂度：$O(mn)$，用于父节点、秩和激活表；返回结果另占 $O(q)$。
若网格很大而实际添加的位置很少，可以改用哈希映射，只为已经激活的位置创建并查集节点，将存储与初始化规模限制到实际陆地数量。那是针对稀疏网格的优化；当前数组实现初始化了全部位置，复杂度中的
mn项不能省略。
关键点总结
[!green]
- 岛数统计的是已激活陆地的连通块，不能直接使用预分配的全部集合数量。
- 新陆地先加一，每次合并两个不同集合才减一，正好维护连通块数量。
- 重复添加与重复连接到同一岛是两种不同的重复，都必须避免重复计数。
易错点总结
[!yellow]
- 编号公式乘的是列数
n，不能误乘行数m。- 已激活位置再次添加时不能加一，也不能漏掉这次操作对应的输出。
- 邻居必须同时满足没有越界、已经是陆地，才能尝试合并。
- 看到一个陆地邻居就减一会重复扣除同一座岛；应以两根不同、合并成功为准。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 200. 岛屿数量 | 中等 | 原题一次给出完整网格，本题逐次新增陆地，需要动态合并相邻连通块。 |
| 684. 冗余连接 | 中等 | 同样用并查集判断新连接是否真正合并两个分量，重复连接不能重复减少分量数。 |
转载与许可
许可
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！