LeetCode 面试题 16.19. 水域大小
目录
题目描述
题意分析
矩阵中 0 表示水，非 0 表示陆地。上下、左右以及四条对角线都算相邻，因此连通规则是八方向。要找出每一片水域的格子数，并把所有大小按升序返回。
题目不是统计 0 的总数，而是按连通分量分组。若从每个 0 都重新搜索却不记录访问状态，同一片水域会被重复计算；若只走四方向，沿对角线接触的水会被错误拆开。
可以直接把已访问的 0 改成 1。这样访问标记复用输入矩阵，不需要额外布尔表；代价是会修改入参，若调用方要求保留原矩阵就应先拷贝。
解法：八方向 DFS 洪水填充
核心思路
扫描矩阵，遇到尚未访问的 0 就启动一次 DFS。DFS 进入格子后立即把它改成 1，再递归八个方向，并返回“当前格子 1 + 所有可达水格子的大小”。
不变量是：一次 DFS 返回时，起点所在水域的所有 0 都恰好被访问并标记一次，返回值等于该连通分量的格子数。提前标记保证相邻格子不会沿反向边再次进入当前格子，所以有环的网格搜索也能终止。
主循环每启动一次 DFS 就得到一个完整水域大小；最后排序即可满足输出顺序。
解题步骤
- 记录行数 m、列数 n，并保存矩阵引用。
- 双层扫描每个格子。
- 若当前位置为 0，调用 DFS，把返回大小加入答案。
- DFS 先把当前位置标成 1，再枚举
[i-1,i+1] × [j-1,j+1]中的九个坐标；自身已被标记，不会重复进入，合法且值为 0 的邻居继续递归。- 扫描结束后升序排序所有水域大小。
例：
land = [[0,2,1,0],[0,1,0,1],[1,1,0,1],[0,1,0,1]]。左上角两个 0 上下相连，大小为 2；右上角 0 通过对角线连接到
(1,2)，再连接(2,2)、(3,2)，大小为 4；左下角(3,0)单独成片，大小为 1。排序后得到[1,2,4]。
代码实现
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) {
int res = 1;
land[i][j] = 1;
for (int x = i - 1; x <= i + 1; ++x) {
for (int y = j - 1; y <= j + 1; ++y) {
if (x >= 0 && x < m && y >= 0 && y < n && land[x][y] == 0) {
res += dfs(x, y);
}
}
}
return res;
}
}
func pondSizes(land [][]int) (answer []int) {
m, n := len(land), len(land[0])
var dfs func(i, j int) int
dfs = func(i, j int) int {
res := 1
land[i][j] = 1
for x := i - 1; x <= i+1; x++ {
for y := j - 1; y <= j+1; y++ {
if x >= 0 && x < m && y >= 0 && y < n && land[x][y] == 0 {
res += dfs(x, 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)。每个格子最多访问一次，p 是水域数量，最后排序需要O(p log p)；由于p <= mn，最坏可写成O(mn log(mn))。- 空间复杂度：
O(mn)最坏递归栈。访问标记复用了原矩阵，不另开O(mn)数组。
关键点总结
- 连通方向是八个，不是常见岛屿题的四个；读题时要先确认邻接定义。
- 进入格子后立刻标记，维持“每个水格只入栈一次”的不变量。
- DFS 返回连通块大小，让搜索与统计在同一个递归里完成。
- 面试追问若要求不修改输入，可增加
visited；若担心递归栈溢出，可用队列或显式栈做 BFS/DFS，复杂度不变。
易错点总结
- 错误写法：只枚举上下左右。上例中的
(0,3)与(1,2)会被拆成两片，输出不再是[1,2,4]。- 递归返回后才标记访问：相邻两个水格会在对方尚未标记时来回递归，最终栈溢出。
- 每次 DFS 使用同一个全局计数却不清零：后一个水域会累加前一个水域的大小。
- 忘记排序：找到的顺序由矩阵位置决定，不保证按大小升序；上例扫描顺序得到
[2,4,1]，题目要求[1,2,4]。- 忽略副作用：当前实现把水改成 1；调用后再次使用原矩阵会看到被修改的数据。
相似题目
| 题目 | 难度 | 考察点 |
|---|---|---|
| 200. 岛屿数量 | 中等 | 四方向连通分量计数 |
| 695. 岛屿的最大面积 | 中等 | DFS 返回连通块面积 |
| 733. 图像渲染 | 简单 | 洪水填充与访问标记 |