首页 LeetCode 系列

# 题目

给你一个 m x n 的矩阵，其中的值均为非负整数，代表二维高度图每个单元的高度，请计算图中形状最多能接多少体积的雨水。

# 示例

# 示例 1

1
2
3
输入: heightMap = [[1,4,3,1,3,2],[3,2,1,3,2,4],[2,3,3,2,3,1]]
输出: 4
解释: 下雨后，雨水将会被上图蓝色的方块中。总的接雨水量为1+2+1=4。

# 示例 2

1
2
输入: heightMap = [[3,3,3,3,3],[3,2,2,2,3],[3,2,1,2,3],[3,2,2,2,3],[3,3,3,3,3]]
输出: 10

# 提示

1
2
3
4
m == heightMap.length
n == heightMap[i].length
1 <= m, n <= 200
0 <= heightMap[i][j] <= 2 * 104

# 相关题目

力扣（LeetCode）407.接雨水II

https://leetcode-cn.com/

# 题解

方家小白-LeetCode题解-42.接雨水

日常积累的代码，知识点, 数据结构与算法的学习与实现，以及例题分享

# 解法

# 解法一

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
public int trapRainWater(int[][] heightMap) {
    if (heightMap.length <= 2 || heightMap[0].length <= 2) {
        return 0;
    }
    int m = heightMap.length;
    int n = heightMap[0].length;
    boolean[][] visit = new boolean[m][n];
    PriorityQueue<int[]> pq = new PriorityQueue<>((o1, o2) -> o1[1] - o2[1]);

    for (int i = 0; i < m; ++i) {
        for (int j = 0; j < n; ++j) {
            if (i == 0 || i == m - 1 || j == 0 || j == n - 1) {
                pq.offer(new int[]{i * n + j, heightMap[i][j]});
                visit[i][j] = true;
            }
        }
    }
    int res = 0;
    int[] dirs = {-1, 0, 1, 0, -1};
    while (!pq.isEmpty()) {
        int[] curr = pq.poll();
        for (int k = 0; k < 4; ++k) {
            int nx = curr[0] / n + dirs[k];
            int ny = curr[0] % n + dirs[k + 1];
            if (nx >= 0 && nx < m && ny >= 0 && ny < n && !visit[nx][ny]) {
                if (curr[1] > heightMap[nx][ny]) {
                    res += curr[1] - heightMap[nx][ny];
                }
                pq.offer(new int[]{nx * n + ny, Math.max(heightMap[nx][ny], curr[1])});
                visit[nx][ny] = true;
            }
        }
    }
    return res;
}

# 最后

期望与你一起遇见更好的自己

期望与你一起遇见更好的自己