LeetCode 面试题 16.19. 水域大小
题目描述
题意分析
矩阵中 0 表示水，非 0 表示陆地。上下、左右以及四条对角线都算相邻，因此连通规则是八方向。要找出每一片水域的格子数，并把所有大小按升序返回。
题目不是统计 0 的总数，而是按连通分量分组。若从每个 0 都重新搜索却不记录访问状态，同一片水域会被重复计算；若只走四方向，沿对角线接触的水会被错误拆开。
可以直接把已发现的 0 改成 1，复用输入矩阵作为访问标记。题目矩阵最多有 $1000\times1000$ 个格子，整片水域会让递归 DFS 形成过深的调用链，因此使用显式栈执行 DFS；这份实现会修改原矩阵。
解法：八方向 DFS 洪水填充
核心思路
[!blue]
扫描矩阵，遇到仍为 0 的格子就开始统计一片新水域。将起点标为 1 并压入栈，之后每次弹出一个水格，将大小加 1，再检查它周围的八个方向。合法且仍为 0 的邻居立刻标记并压栈，等待后续处理。
标记必须发生在压栈时，不能等弹出后才做，否则同一个水格可能被多个邻居重复压入。所有入栈格子都能从起点沿水格到达；反过来，任一与起点连通的水格，都可以沿某条相邻路径被逐步发现。因此栈为空时，恰好处理完这一片水域，每个水格只贡献一次计数。
栈中用
row * n + col保存坐标，弹出后通过除以n、对n取余还原行列。这样只保存一个整数即可表示一个格子，最多百万格的下标也在整数范围内。邻居循环枚举周围九个位置，其中中心格已被标记，会自然跳过，实际仍只扩展八方向。一次搜索会把整片水域全部标记，后续行列扫描不会再次启动同一片水域。搜索得到的大小按发现位置排列，与大小无关，所以最后还要统一升序排序。全为陆地时不启动搜索，直接返回空结果。
解题步骤
- 记录行列数，逐格扫描，遇到 0 时启动一次 DFS。
- 将起点编码入栈并立即标记，水域大小从 0 开始。
- 弹出一个格子并计数，检查周围八个邻居；对合法的未发现水格先标记再压栈。
- 栈空时返回这片水域的大小，加入答案后继续行列扫描。
- 将所有水域大小升序排序并返回。
代码实现
class Solution {
private int m;
private int n;
private int[][] land;
public int[] pondSizes(int[][] land) {
m = land.length;
n = land[0].length;
this.land = land;
List<Integer> answer = new ArrayList<>();
for (int i = 0; i < m; ++i) {
for (int j = 0; j < n; ++j) {
if (land[i][j] == 0) {
answer.add(dfs(i, j));
}
}
}
return answer.stream().sorted().mapToInt(Integer::valueOf).toArray();
}
private int dfs(int i, int j) {
Deque<Integer> stack = new ArrayDeque<>();
stack.push(i * n + j);
land[i][j] = 1;
int res = 0;
while (!stack.isEmpty()) {
int cell = stack.pop();
int row = cell / n;
int col = cell % n;
res++;
for (int x = row - 1; x <= row + 1; ++x) {
for (int y = col - 1; y <= col + 1; ++y) {
if (x >= 0 && x < m && y >= 0 && y < n && land[x][y] == 0) {
land[x][y] = 1;
stack.push(x * n + y);
}
}
}
}
return res;
}
}
import (
"sort"
)
func pondSizes(land [][]int) (answer []int) {
m, n := len(land), len(land[0])
dfs := func(i, j int) int {
stack := []int{
i*n + j,
}
land[i][j] = 1
res := 0
for len(stack) > 0 {
cell := stack[len(stack)-1]
stack = stack[:len(stack)-1]
row, col := cell/n, cell%n
res++
for x := row - 1; x <= row+1; x++ {
for y := col - 1; y <= col+1; y++ {
if x >= 0 && x < m && y >= 0 && y < n && land[x][y] == 0 {
land[x][y] = 1
stack = append(stack, x*n+y)
}
}
}
}
return res
}
for i := range land {
for j := range land[i] {
if land[i][j] == 0 {
answer = append(answer, dfs(i, j))
}
}
}
sort.Ints(answer)
return
}
复杂度分析
- 时间复杂度：$O(mn+p\log(p+1))$，其中 $p$ 为水域数量。每个水格只入栈、出栈一次，每次检查常数个邻居，最后排序全部水域大小。
- 空间复杂度：$O(mn)$，用于最坏情况下的显式栈及结果列表。访问标记复用原矩阵，不再依赖递归调用栈。
关键点总结
[!green]
- 连通方向是八个，不是常见岛屿题的四个；读题时要先确认邻接定义。
- 发现水格时立刻标记，维持“每个水格只入栈一次”的不变量。
- 每次搜索独立计数并返回连通块大小，不让不同水域的统计混在一起。
- 显式栈保存待处理格子，避免大水域导致调用栈过深。
易错点总结
[!yellow]
- 只枚举上下左右：仅对角相连的水格会被错误拆成不同水域。
- 弹出后才标记访问：一个水格可能被多个邻居重复压栈，造成重复计数。
- 每次 DFS 使用同一个全局计数却不清零：后一个水域会累加前一个水域的大小。
- 忘记排序：发现顺序由矩阵位置决定，不能保证水域大小升序。
- 忽略副作用：当前实现把水改成 1；调用后再次使用原矩阵会看到被修改的数据。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 695. 岛屿的最大面积 | 中等 | 同样统计连通块面积，本题水为0且使用八方向，原题使用四方向。 |
| 200. 岛屿数量 | 中等 | 从统计连通块个数扩展为返回每块大小，访问标记方法相同。 |
转载与许可
许可
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！