题目
LC 200 岛屿数量：给你一个由
'1'（陆地）和
'0'（水）组成的二维网格
grid，请你计算网格中
岛屿的数量。岛屿总是被水包围，并且每座岛屿只能由
水平方向和/或
竖直方向上相邻的陆地连接而成。你可以假设网格的四条边均被水包围。
输入: grid = [
["1","1","1","1","0"],
["1","1","0","1","0"],
["1","1","0","0","0"],
["0","0","0","0","0"]
]
输出: 1
输入: grid = [
["1","1","0","0","0"],
["1","1","0","0","0"],
["0","0","1","0","0"],
["0","0","0","1","1"]
]
输出: 3
一个
3 × 3 全是陆地的网格（你题面里的例子）→ 输出
1，因为九块陆地水平竖直全连通，是
一座岛。注意
'1'/
'0' 是
字符，也
只有上下左右四个方向算连通，对角线不算。
这题的骨架短到一句话：
扫描整个网格，每遇到一块"还没被访问过的"陆地，答案 +1，然后把与它连通的整座岛一次性"淹掉"（标记为已访问）。
剩下的全部区别，只在于"淹掉一座岛"这一步用什么实现 —— 递归 DFS、显式栈 DFS、BFS 队列，还是并查集。而
追问里最值钱的那一问（网格大了 DFS 会怎样）答案就藏在这里：
递归 DFS 的递归深度等于整座岛最长的连通路径，一条蛇形长岛足以撑爆调用栈。
一、核心洞察：数岛屿 = 数连通块
把每个陆地格子看成图上的一个点，上下左右相邻就有一条边。
岛屿数量 = 这张图的连通块数量（只看陆地点）。于是有两条互为镜像的路：
- 染色法（flood fill）：扫描到一块未访问的陆地，就把它所在的整个连通块"染"一遍（DFS / BFS），同时计数
+1；
- 并查集法（union-find）：把每块陆地先当一个独立集合，遇到相邻陆地就合并，最后剩余集合数 = 岛屿数。
两者都在回答同一个问题："哪些陆地连在一起"。代码骨架：
def numIslands(grid):
if not grid:
return 0
m, n = len(grid), len(grid[0])
seen = [[False] * n for _ in range(m)]
count = 0
for r in range(m):
for c in range(n):
if grid[r][c] == "1" and not seen[r][c]:
count += 1 # 发现一座新岛
flood(grid, r, c, seen) # 把整座岛淹掉
return count
三个细节决定成败：
- 只对"未被访问的陆地"计数。水和已访问的陆地都直接跳过 —— 计数发生在"第一次碰到这座岛"的瞬间，一次一座，不多不少。
- 标记访问要"一入就标"，不能"出了才标"（BFS/栈都适用）。入队/入栈时立刻置
seen，否则同一块陆地在被处理前会被多个邻居重复塞进去，队列爆炸甚至超时。
visited 可以独立开数组，也可以原地把 '1' 改成 '0'。原地改省空间，但会破坏输入；面试里最好问一句"能不能改原数组"。
二、递归 DFS 为什么会爆栈
flood 的最简写法是递归：
def flood(grid, r, c, seen):
if r < 0 or r >= len(grid) or c < 0 or c >= len(grid[0]):
return
if grid[r][c] != "1" or seen[r][c]:
return
seen[r][c] = True
flood(grid, r - 1, c, seen)
flood(grid, r + 1, c, seen)
flood(grid, r, c - 1, seen)
flood(grid, r, c + 1, seen)
代码短、好写，但它有一个
隐藏的 O(岛屿大小) 调用栈：每深入一层连通路径就压一个栈帧。递归深度 = 从入口到最远处的那条
最长无重复连通路径。
问题在于，这个深度可以很大：
- 一条蛇形长岛（比如单行
1 连绵、或首尾相接的回形走廊）能让深度 ≈ 陆地总数。LC 约束 m, n ≤ 300，最坏 90000 块陆地全连通 → 递归深度 90000。
- Python 默认递归上限只有 1000（
sys.getrecursionlimit()）→ 直接 RecursionError；Java 的线程栈约几百 KB~1MB，深递归必 StackOverflowError。
所以"递归 DFS 能过"是有条件的：
得赌测试数据里没有长条连通块。两三万的网格里随便一条蛇就能让它崩。两条出路：
要么把递归换成显式栈（把调用栈搬到堆上），要么干脆换数据结构（BFS / 并查集）。
一句话总结这一节：
DFS 的空间 = visited（O(m·n)）+ 递归深度（最坏 O(m·n)）；爆的不是内存，是调用栈的深度上限。
三、动画怎么看
动画一（
algo-viz--lc200）：
染色法。左边是网格，陆地深色、水浅色、已访问的陆地染灰；右上是一条
显式栈（从栈底到栈顶列出坐标），右下是"岛屿计数"。每发一帧：
seed 帧是"扫描到一块新陆地 →
count+1、入栈"（计数格描金）；
pop 帧从栈顶弹出一块，把它四周
未被访问的陆地（描绿）标记并压栈。盯住两件事：
新岛只在 seed 帧计数，以及
栈的深度会随连通块大小起伏 —— 这正是递归版"调用栈深度"的可视化。
动画二（
algo-viz--lc200uf）：
并查集。每块陆地初始各自成集合（
count 从 0 起，每加一块
+1）；扫描时把它和
上方、左方已经处理过的陆地合并 —— 合并成功一次，
count-1。网格里每块陆地标着它当前的
根坐标，相同根同色。盯住计数格：
加一块 +1、成功合并 -1，一趟扫完，剩下的就是岛屿数。它
全程没有递归、没有栈，深度安全。
两个动画是对同一张网格、同一个答案（
3）的两种看法：动画一"从一块陆地扩散出去"，动画二"把相邻陆地并起来"。
四、完整推演表
动画一（DFS 染色）：网格
1 1 0 0 0
1 1 0 0 0
0 0 1 0 0
0 0 0 1 1
三座岛：左上
2×2、中央单块
(2,2)、右下两块
(3,3)(3,4)。约定邻居入栈顺序为
上、右、下、左，栈是 LIFO，所以
后入先出。逐帧如下：
扫描到
(0,1)、
(1,0)、
(1,1) 时它们
已被染色，直接跳过，不再计数 —— 这就是"每座岛只 +1 一次"的保证。最终
count = 3。
动画二（并查集）：同一张网格，按行优先扫描，每块陆地和
上方、左方合并：
最终
count = 3，与染色法一致。注意
(1,1) 那行：它和上方、左方
本就同根，两次合并都跳过 —— 并查集用"根是否相同"天然去重，不需要
visited。
五、防爆栈的两条路：BFS 与并查集
BFS：把递归的调用栈换成队列。同一段洪水逻辑，只是访问顺序从 LIFO 变 FIFO —— 递归 DFS 和 BFS 的差别
只有一行（栈 vs 队列）：
from collections import deque
def numIslands_bfs(grid):
if not grid:
return 0
m, n = len(grid), len(grid[0])
count = 0
for r in range(m):
for c in range(n):
if grid[r][c] != "1":
continue
count += 1
grid[r][c] = "0" # 入队即标记，防止重复入队
q = deque([(r, c)])
while q:
x, y = q.popleft()
for dx, dy in ((1, 0), (-1, 0), (0, 1), (0, -1)):
nx, ny = x + dx, y + dy
if 0 <= nx < m and 0 <= ny < n and grid[nx][ny] == "1":
grid[nx][ny] = "0" # 关键：入队时就标记
q.append((nx, ny))
return count
同理，只把
deque 换成
list 的
append/
pop —— 深度不再受调用栈限制，代价是栈内容存在
堆里。
并查集：数连通块，全程无递归：
def numIslands_uf(grid):
if not grid:
return 0
m, n = len(grid), len(grid[0])
parent = {}
def find(x):
root = x
while parent[root] != root:
root = parent[root]
while parent[x] != root: # 路径压缩
parent[x], x = root, parent[x]
return root
count = 0
for r in range(m):
for c in range(n):
if grid[r][c] != "1":
continue
parent[(r, c)] = (r, c)
count += 1 # 先各自成一个集合
for pr, pc in ((r - 1, c), (r, c - 1)):
if 0 <= pr < m and 0 <= pc < n and grid[pr][pc] == "1":
a, b = find((r, c)), find((pr, pc))
if a != b:
parent[a] = b # 合并
count -= 1 # 合并成功，连通块少一个
return count
并查集的好处很实在：
它没有递归、没有显式栈、也不依赖"一入就标"；而且当题目要
动态加陆地（LC 305 岛屿数量 II）时，只有它能增量维护答案 —— 这正是它在面试追问里被点名的原因。
三条路的取舍：
六、Java 版
class Solution {
// 显式栈 DFS：把"递归深度"搬到堆上的 Stack，避免 StackOverflowError
private static final int[][] DIRS = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
public int numIslands(char[][] grid) {
if (grid == null || grid.length == 0) return 0;
int m = grid.length, n = grid[0].length, count = 0;
for (int r = 0; r < m; r++) {
for (int c = 0; c < n; c++) {
if (grid[r][c] != '1') continue;
count++;
grid[r][c] = '0'; // 入栈即标记
Deque<int[]> stack = new ArrayDeque<>();
stack.push(new int[]{r, c});
while (!stack.isEmpty()) {
int[] cur = stack.pop();
for (int[] d : DIRS) {
int nx = cur[0] + d[0], ny = cur[1] + d[1];
if (nx >= 0 && nx < m && ny >= 0 && ny < n && grid[nx][ny] == '1') {
grid[nx][ny] = '0';
stack.push(new int[]{nx, ny});
}
}
}
}
}
return count;
}
}
class Solution {
// 并查集：数连通块，全程无递归
private int[] parent, rank;
public int numIslands(char[][] grid) {
if (grid == null || grid.length == 0) return 0;
int m = grid.length, n = grid[0].length;
parent = new int[m * n];
rank = new int[m * n];
int count = 0;
for (int r = 0; r < m; r++) {
for (int c = 0; c < n; c++) {
if (grid[r][c] == '1') {
int id = r * n + c;
parent[id] = id;
count++;
}
}
}
for (int r = 0; r < m; r++) {
for (int c = 0; c < n; c++) {
if (grid[r][c] != '1') continue;
int id = r * n + c;
if (r + 1 < m && grid[r + 1][c] == '1' && union(id, (r + 1) * n + c)) count--;
if (c + 1 < n && grid[r][c + 1] == '1' && union(id, r * n + c + 1)) count--;
}
}
return count;
}
private int find(int x) {
while (parent[x] != x) {
parent[x] = parent[parent[x]]; // 路径压缩（隔代压缩）
x = parent[x];
}
return x;
}
private boolean union(int a, int b) {
int ra = find(a), rb = find(b);
if (ra == rb) return false;
if (rank[ra] < rank[rb]) { int t = ra; ra = rb; rb = t; }
parent[rb] = ra;
if (rank[ra] == rank[rb]) rank[ra]++;
return true;
}
}
一个 Java 细节：
new int[m*n] 对
300×300 是
90000，没问题；但如果网格更大，可以把
parent 用
int[] 继续压（无需
Map）。
union 返回"是否真的合并了"，正好用来决定
count--。
七、同族题：695 / 130 / 463 / 1254 / 733 / 694 / 1905 / 1020
200 是"网格连通块"这一族的原点，换个问法就是一条完整题链：
- LC 695 岛屿的最大面积：200 的染色逻辑，把
count++ 换成"累加本次淹掉的格子数"，取最大值。
- LC 130 被围绕的区域：先对四条边上的
'O' 各做一次染色（这些连通块"逃得掉"），再把剩下的 'O' 全变 'X'。边界上的连通块是这题的唯一陷阱。
- LC 463 岛屿的周长：不染色也行 —— 每块陆地贡献
4，每条相邻的陆地边抵消 2。
- LC 1254 统计封闭岛屿的数目：先淹掉贴边的陆地，再数剩下的岛屿。
- LC 733 图像渲染：把"相邻"从上下左右换成"同色"，就是最纯粹的 flood fill。
- LC 694 不同岛屿的数量：染色时记录形状（相对坐标序列 / 转向串），去重 —— 同一套 DFS，多了个"签名"。
- LC 1905 统计子岛屿：两座网格逐格"与"，再数连通块。
- LC 1020 飞地的数量：等价于"数不贴边的陆地块数"。
- LC 305 岛屿数量 II（会员/进阶）：逐个加陆地，正是并查集的主场 —— 每次加一格，把它和已有陆地合并，增量输出答案。
把它们排成一列看：
网格连通块的骨架永远是"扫描 + 把一整块处理掉"；剩下的差别只在"处理时记什么"（面积 / 形状 / 贴不贴边）和"用什么容器"（递归栈 / 显式栈 / 队列 / 并查集）。
八、边界情况
- 空网格：
grid == [] 或某行长度为 0，直接返回 0（写代码先判空）；
- 全水：扫完没有陆地，返回
0；
- 全陆地：任何连通（只要
m,n ≥ 1）→ 返回 1；3 × 3 全陆地的例子就是它；
1 × 1："1" → 1，"0" → 0；- 单行 / 单列：退化成链，DFS 递归深度 = 长度 —— 最容易触发爆栈的形态；
- 长蛇形连通块：
m·n 全连通时，递归 DFS 深度可达 90000，Python 默认上限 1000 必挂；
- 原地修改：把
'1' 改成 '0' 会破坏输入，某些在线评测多组用例复用同一网格时要留意；
- 大网格的对角相邻：
"1" 斜着挨在一起不算连通，别误用八方向。
九、复杂度
m、
n 是网格行数、列数，
α 是反阿克曼函数（实际接近常数）。
时间上四者都是 O(m·n) —— 每块陆地至多被"访问"常数次、每条邻接边至多被检查常数次。真正拉开差距的是
空间的性质：递归 DFS 把
O(m·n) 压在
调用栈上（有硬上限、会爆），其余把开销放在
堆上（可通过
visited 与容器复用控制）。
十、常见坑
- BFS/栈"出队才标记"：入队时不标
visited，同一格会被多个邻居反复入队，队列膨胀甚至 MLE。入队/入栈的那一刻就标记。
- 递归 DFS 没防爆栈：Python 默认递归上限 1000，Java 栈也有限；长蛇形网格直接
RecursionError / StackOverflowError。换显式栈 / BFS / 并查集，或临时 sys.setrecursionlimit（治标不治本）。
- 把
'1'/'0' 当整数：网格里是字符，比较要写 grid[r][c] == "1"（Java 里是 == '1'），写成 == 1 恒假。
- 方向写成八个：只有上下左右四个方向算连通，斜着不算。
- 边界检查缺失或写反：
0 <= nx < m and 0 <= ny < n 少一个就数组越界。
- 并查集忘记
count--：合并成功却没把计数减 1，最后数出的岛屿数偏大。用 union 的返回值驱动 count-- 最稳。
- 并查集方向搞乱：只跟已处理过的邻居（上 / 左，或右 / 下，二选一）合并即可；两个方向都合会重复（虽然结果对，但多做功）。
- 原地改数组后又想复用：
'1'→'0' 破坏输入；需要保留原网格时改用独立 visited。
- 忘了判空：
grid[0] 在 grid == [] 时直接越界。
- 把
visited 和 grid 判反：seen 只对陆地有意义，水和已访问陆地都要跳过，但理由不同（前者不是岛，后者已算过）。
十一、面试怎么答
第一段 · 骨架：数岛屿 = 数网格里的连通块。扫描全网格，遇到未访问的陆地就
count++ 并做一次 flood fill 把整座岛标记掉。递归 DFS 最短，
O(m·n)。
第二段 · 主动补爆栈（
这段是区分度所在）：递归 DFS 的
递归深度 = 最长连通路径，最坏
O(m·n)；蛇形长岛会
RecursionError（Python 默认上限 1000）/
StackOverflowError（Java）。两条出路：
显式栈 / BFS 队列（把栈搬到堆上，逻辑只差"LIFO 换 FIFO"），或
并查集（数连通块，全程无递归）。
第三段 · 并查集与进阶：并查集把每块陆地先当独立集合，相邻就合并，
剩余集合数 即答案；它的杀手锏是
动态加陆地时能增量维护 —— 见 LC 305。
追问连跳：
- 要
最大面积 → LC 695，把计数换成累加；
- 要
封闭岛屿 / 飞地 → LC 1254 / 1020，先淹贴边的；
- 要
被围绕的区域 → LC 130，先对四条边的连通块染色；
- 要
不同形状的岛屿 → LC 694，染色时记形状签名；
- 要
动态加陆地 → LC 305，并查集增量维护。
一句话收尾："岛屿数量只有一台机器 ——
扫描 + 把一整块连通陆地处理掉；DFS 是它最简的实现，BFS/显式栈/并查集是它防爆栈的三个替身。"
结语
200 的全部难度浓缩在一行骨架里：扫描 + 遇到新陆地就染色、计数。真正让它在面试里分层的，是
"染色用什么写"这个追问 —— 递归 DFS 最简却有
O(m·n) 的调用栈深度，长蛇形网格一定爆；把栈搬到堆上（显式栈 / BFS）或换成并查集，就能把"深度"这件事从算法里彻底拿掉。记住那句判据：
每块陆地只数一次，每座岛只加一次。
下一篇见。