水域大小

你有一个用于表示一片土地的整数矩阵land，该矩阵中每个点的值代表对应地点的海拔高度。若值为0则表示水域。由垂直、水平或对角连接的水域为池塘。池塘的大小是指相连接的水域的个数。编写一个方法来计算矩阵中所有池塘的大小，返回值需要从小到大排序。

示例：

输入：
[
  [0,2,1,0],
  [0,1,0,1],
  [1,1,0,1],
  [0,1,0,1]
]
输出： [1,2,4]
提示：

0 < len(land) <= 1000
0 < len(land[i]) <= 1000
通过次数12,279提交次数20,363

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/pond-sizes-lcci
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

class Solution {
    int count = 0;

    public int[] pondSizes(int[][] land) {
        if (land == null || land.length == 0 || land[0].length == 0) return new int[]{0};

        PriorityQueue<Integer> pq = new PriorityQueue<>();

        boolean vis[][] = new boolean[land.length][land[0].length];
        for (int i = 0; i < land.length; i++) {
            for (int j = 0; j < land[0].length; j++) {

                if (land[i][j] == 0 && !vis[i][j]) {
                    count = 0;
                    deep(land, vis, i, j);
                    pq.offer(count);
                }
            }
        }

        int[] res = new int[pq.size()];
        int index = 0;
        while (!pq.isEmpty()) {
            res[index] = pq.poll();
            index++;
        }

        return res.length == 0 ? new int[]{0} : res;
    }

    public void deep(int[][] land, boolean[][] vis, int y, int x) {
        if (x >= land[0].length || x < 0 || y >= land.length || y < 0 || vis[y][x]) return;

        if (land[y][x] == 0) {
            count++;
            vis[y][x] = true;
            deep(land, vis, y + 1, x + 1);
            deep(land, vis, y + 1, x);
            deep(land, vis, y, x + 1);
            deep(land, vis, y + 1, x - 1);
            deep(land, vis, y - 1, x - 1);
            deep(land, vis, y - 1, x);
            deep(land, vis, y, x - 1);
            deep(land, vis, y - 1, x + 1);
        }
    }
}

赏

谢谢你请我吃糖果

微信