面试题 16.19. 池塘大小 - Pond Sizes

🎯 问题描述（来源于LeetCode）

描述：
给定一个 m x n 的整数矩阵 land，其中：

0 表示池塘（水域）。
正整数表示陆地。
池塘是八方向（上、下、左、右、以及对角线方向）连通的 0 区域。
请返回所有池塘的大小（即每个池塘中包含的 0 的数量），并将结果按从小到大排序。

说明：

八方向连通包括水平、垂直和对角线相邻。
池塘的边界由陆地（正整数）或网格边界限定。

示例：

示例 1：

输入:
land = [
  [0,2,1,0],
  [0,1,0,1],
  [1,1,0,1],
  [0,1,0,1]
]
输出: [1,2,4]
解释: 左上角池塘大小为1（一个0），右上角池塘大小为2，中间池塘大小为4。

💻 解题思路

思路1：DFS 遍历八方向连通分量

算法步骤

初始化：
- 获取网格尺寸 m, n。
- 创建 visited 二维数组，标记已访问的格子。
- 定义八方向偏移量：
  [(-1,-1),(0,-1),(1,-1),(-1,0),(1,0),(-1,1),(0,1),(1,1)]。
- 结果列表 ans = []。
定义 DFS 函数 dfs(i, j)：
- 返回当前池塘的大小（包含当前格子）。
- 标记 (i, j) 为已访问。
- 初始化 size = 1。
- 遍历八个方向：新坐标 (di, dj)，如果合法、未访问且 land[di][dj] == 0，则递归调用 dfs(di, dj) 并将返回值累加到 size。
- 返回 size。
遍历所有格子：
- 对于每个格子 (i, j)，如果它是池塘（值为 0）且未被访问，则调用 dfs(i, j) 得到池塘大小，加入 ans。
排序并返回：
- 对 ans 从小到大排序，返回排序后的列表。

思路1：代码实现

from typing import List

class Solution:
    def pondSizes(self, land: List[List[int]]) -> List[int]:
        m, n = len(land), len(land[0])
        visited = [[False] * n for _ in range(m)]
        direction = [(-1,-1),(0,-1),(1,-1),
                     (-1,0),(1,0),
                     (-1,1),(0,1),(1,1)]
        ans = []
        
        def dfs(i, j):
            visited[i][j] = True
            size = 1
            for dx, dy in direction:
                di, dj = i + dx, j + dy
                if 0 <= di < m and 0 <= dj < n and not visited[di][dj] and land[di][dj] == 0:
                    size += dfs(di, dj)
            return size
        
        for i, row in enumerate(land):
            for j, x in enumerate(row):
                if not visited[i][j] and land[i][j] == 0:
                    size = dfs(i, j)
                    ans.append(size)
        ans.sort()
        return ans

思路1：📊 性能分析

时间复杂度： $O(m \times n)$ ，每个格子最多访问一次，对每个访问的格子检查 8 个邻居。
空间复杂度： $O(m \times n)$ ，visited 数组占用额外空间，递归栈深度最坏为池塘大小（可能接近 $m \times n$ ）。

思考

本题与 LeetCode 200（[[岛屿数量]]）的区别在于：本题是八方向连通，且统计的是 0 区域的面积（大小），而岛屿数量是四方向且统计的是 1 的区域数量。
也可以用 BFS 实现，使用队列代替递归，避免深度过大导致栈溢出。
注意：题目要求结果按从小到大排序，因此需要对 ans 排序后返回。