README_EN.md

407. Trapping Rain Water II

中文文档

Description

Given an m x n integer matrix heightMap representing the height of each unit cell in a 2D elevation map, return the volume of water it can trap after raining.

 

Example 1:

Input: heightMap = [[1,4,3,1,3,2],[3,2,1,3,2,4],[2,3,3,2,3,1]]
Output: 4
Explanation: After the rain, water is trapped between the blocks.
We have two small ponds 1 and 3 units trapped.
The total volume of water trapped is 4.

Example 2:

Input: 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]]
Output: 10

 

Constraints:

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

Solutions

Python3

class Solution:
    def trapRainWater(self, heightMap: List[List[int]]) -> int:
        m, n = len(heightMap), len(heightMap[0])
        vis = [[False] * n for _ in range(m)]
        pq = []
        for i in range(m):
            for j in range(n):
                if i == 0 or i == m - 1 or j == 0 or j == n - 1:
                    heappush(pq, (heightMap[i][j], i, j))
                    vis[i][j] = True

        ans = 0
        while pq:
            e = heappop(pq)
            for x, y in [[0, 1], [0, -1], [1, 0], [-1, 0]]:
                i, j = e[1] + x, e[2] + y
                if i >= 0 and i < m and j >= 0 and j < n and not vis[i][j]:
                    if heightMap[i][j] < e[0]:
                        ans += e[0] - heightMap[i][j]
                    vis[i][j] = True
                    heappush(pq, (max(heightMap[i][j], e[0]), i, j))
        return ans

Java

class Solution {
    public int trapRainWater(int[][] heightMap) {
        int m = heightMap.length, n = heightMap[0].length;
        boolean[][] vis = new boolean[m][n];
        PriorityQueue<int[]> pq = new PriorityQueue<>((o1, o2) -> o1[0] - o2[0]);
        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[] {heightMap[i][j], i, j});
                    vis[i][j] = true;
                }
            }
        }
        int ans = 0;
        int[][] dirs = new int[][] {{0, -1}, {0, 1}, {1, 0}, {-1, 0}};
        while (!pq.isEmpty()) {
            int[] e = pq.poll();
            for (int[] d : dirs) {
                int i = e[1] + d[0], j = e[2] + d[1];
                if (i >= 0 && i < m && j >= 0 && j < n && !vis[i][j]) {
                    if (heightMap[i][j] < e[0]) {
                        ans += e[0] - heightMap[i][j];
                    }
                    vis[i][j] = true;
                    pq.offer(new int[] {Math.max(heightMap[i][j], e[0]), i, j});
                }
            }
        }
        return ans;
    }
}

...