Interview.P1619[水域大小]

方法一：DFS

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
class Solution {
    
    int m, n;
    int[][] land;

    public int[] pondSizes(int[][] land) {
        this.land = land;
        m = land.length;
        n = land[0].length;
        List<Integer> list = new ArrayList<>();
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                if (land[i][j] == 0) {
                    list.add(dfs(i, j));
                }
            }
        }
        // 简洁，运行速度慢
        // return list.stream().sorted().mapToInt(Integer::valueOf).toArray();

        // 麻烦，运行速度快
        int[] ans = new int[list.size()];
        for (int i = 0; i < list.size(); ++i) {
            ans[i] = list.get(i);
        }
        Arrays.sort(ans);
        return ans;
    }

    private int dfs(int i, int j) {
        int ans = 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) continue;
                ans += dfs(x, y);
            }
        }
        return ans;
    }
}
  • 时间复杂度：$O(mn)$
  • 空间复杂度：$O(mn)$