算法与数据结构 · 实战

LC:42.接雨水

本文写于 2021 年,涉及的组件版本、配置与数据可能已过时,请按经验材料阅读并核对当前版本。原文链接与内容保持不变。

题目

给定 n 个非负整数表示每个宽度为 1 的柱子的高度图,计算按此排列的柱子,下雨之后能接多少雨水。

示例 1:

输入:height = [0,1,0,2,1,0,1,3,2,1,2,1]
输出:6
解释:上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图,在这种情况下,可以接 6 个单位的雨水(蓝色部分表示雨水)。 

示例 2:

输入:height = [4,2,0,3,2,5]
输出:9

提示

n == height.length
1 <= n <= 2 * 104
0 <= height[i] <= 105

相关题目

相关链接

题解

相关链接

解法

解法一

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;
}

最后

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

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

配套资料 · 免费领取
本文属于「ALGO」资料包范围:算法系列合订 + 刷题清单。LeetCode 与杭电 OJ 的题解索引。
在公众号「方家小白」回复关键词 ALGO 即可领取。全文无需关注即可阅读。
ALGO