407. Trapping Rain Water II

Created: 09/26/2021

Leetcode

Basic Idea:

这道题的解法还是要模拟从四周的墙最矮的地方向内部灌水的过程，因为是雨水，实际上我们需要在过程中出现了由更高的墙围起来的空间的时候在相对较低的地方继续灌水。我们可以利用一个优先队列，先将四周的墙加入队列，然后从最低的部分开始灌水，如果遇到更高的墙，则要将其加入PQ。需要另外维持一个变量记录当前内部的最高水位（最低的墙的高度），由于墙一直在外面，所以这个最高水位不会下降，只会在当当前PQ 的peek高度高于该水位的时候更新为pq.peek。

可以理解为PQ维持了墙的内圈高度。

Java Code:

class Solution {
    public int trapRainWater(int[][] heightMap) {
        PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> {
            return Integer.compare(heightMap[a[0]][a[1]], heightMap[b[0]][b[1]]);
        });
        int R = heightMap.length, C = heightMap[0].length;
        boolean[][] visited = new boolean[R][C];
        // 先将四周的墙填入pq
        for (int r = 0; r < R; ++r) {
            visited[r][0] = true;
            visited[r][C - 1] = true;
            pq.offer(new int[] {r, 0});
            pq.offer(new int[] {r, C - 1});
        }
        for (int c = 1; c < C - 1; ++c) {
            visited[0][c] = true;
            visited[R - 1][c] = true;
            pq.offer(new int[] {0, c});
            pq.offer(new int[] {R - 1, c});
        }
        
        int water = 0;
        int maxWaterHeight = 0;
        int[] dr = new int[] {0, 1, 0, -1};
        int[] dc = new int[] {1, 0, -1, 0};
        while (!pq.isEmpty()) {
            int[] curr = pq.poll();
            maxWaterHeight = Math.max(maxWaterHeight, heightMap[curr[0]][curr[1]]);
            for (int i = 0; i < 4; ++i) {
                int newR = curr[0] + dr[i];
                int newC = curr[1] + dc[i];
                if (newR >= 0 && newR < R && newC >= 0 && newC < C 
                    && !visited[newR][newC]) {
                    visited[newR][newC] = true;
                    pq.offer(new int[] {newR, newC});
                    if (heightMap[newR][newC] < maxWaterHeight) {
                        water += maxWaterHeight - heightMap[newR][newC];
                    }
                }
            }
        }
        return water;
    }
}