Welcome to Subscribe On Youtube
Formatted question description: https://leetcode.ca/all/407.html
407. Trapping Rain Water II
Level
Hard
Description
Given an m x n matrix of positive integers representing the height of each unit cell in a 2D elevation map, compute the volume of water it is able to trap after raining.
Note:
Both m and n are less than 110. The height of each unit cell is greater than 0 and is less than 20,000.
Example:
Given the following 3x6 height map:
[
[1,4,3,1,3,2],
[3,2,1,3,2,4],
[2,3,3,2,3,1]
]
Return 4.
The above image represents the elevation map [[1,4,3,1,3,2],[3,2,1,3,2,4],[2,3,3,2,3,1]] before the rain.
After the rain, water is trapped between the blocks. The total volume of water trapped is 4.
Solution
If height has length 0, then return 0.
Use priority queue and breadth first search. For each cell, store its row, column and height.
To calculate the amount of water trapped in a terrain, start by adding all the cells on the border of the terrain to a priority queue. Each cell’s height is compared, and the cell with the smallest height is polled first.
After a cell is polled from the queue, its adjacent cells are considered. If an adjacent cell has a lower height, then water is trapped in that cell. Calculate the amount of water trapped by taking the difference in height between the two cells, add that amount to the result, and offer the adjacent cell to the priority queue with the height of the current cell.
If an adjacent cell has a greater height, then that cell will not have any trapped water. Simply offer the adjacent cell to the priority queue using its own height.
Finally, return the total amount of trapped water.
-
class Solution { public int trapRainWater(int[][] heightMap) { if (heightMap == null || heightMap.length == 0 || heightMap[0].length == 0) return 0; int rows = heightMap.length, columns = heightMap[0].length; boolean[][] visited = new boolean[rows][columns]; PriorityQueue<Cell> priorityQueue = new PriorityQueue<Cell>(); // top/bottom border process for (int i = 0; i < columns; i++) { visited[0][i] = true; visited[rows - 1][i] = true; priorityQueue.offer(new Cell(0, i, heightMap[0][i])); priorityQueue.offer(new Cell(rows - 1, i, heightMap[rows - 1][i])); } // left/right border process for (int i = 1; i < rows - 1; i++) { visited[i][0] = true; visited[i][columns - 1] = true; priorityQueue.offer(new Cell(i, 0, heightMap[i][0])); priorityQueue.offer(new Cell(i, columns - 1, heightMap[i][columns - 1])); } int amount = 0; int[][] directions = { {-1, 0}, {1, 0}, {0, -1}, {0, 1} }; while (!priorityQueue.isEmpty()) { while (!priorityQueue.isEmpty()) { // 第一次poll出来的，是整个3D地图的4个border上的最低点 int row = cell.row, column = cell.column, height = cell.height; for (int[] direction : directions) { int newRow = row + direction[0], newColumn = column + direction[1]; if (newRow >= 0 && newRow < rows && newColumn >= 0 && newColumn < columns) { if (!visited[newRow][newColumn]) { visited[newRow][newColumn] = true; int newCellHeight = heightMap[newRow][newColumn]; if (height > newCellHeight) { // always enque with higher height amount += height - newCellHeight; priorityQueue.offer(new Cell(newRow, newColumn, height)); } else priorityQueue.offer(new Cell(newRow, newColumn, newCellHeight)); } } } } return amount; } } class Cell implements Comparable<Cell> { int row; int column; int height; public Cell(int row, int column, int height) { this.row = row; this.column = column; this.height = height; } public int compareTo(Cell cell2) { return this.height - cell2.height; } } -
// OJ: https://leetcode.com/problems/trapping-rain-water-ii/ // Time: O(MNlog(MN)) // Space: O(MN) // Ref: https://discuss.leetcode.com/topic/60914/concise-c-priority_queue-solution class Solution { typedef array<int, 3> Point; public: int trapRainWater(vector<vector<int>>& A) { int M = A.size(), N = A[0].size(), dirs[4][2] = { {0,1},{0,-1},{1,0},{-1,0} }, ans = 0, maxH = INT_MIN; priority_queue<Point, vector<Point>, greater<>> pq; vector<vector<bool>> seen(M, vector<bool>(N)); 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.push({ A[i][j], i, j }); seen[i][j] = true; } } } while (pq.size()) { auto [h, x, y] = pq.top(); pq.pop(); maxH = max(maxH, h); for (auto &[dx, dy] : dirs) { int a = x + dx, b = y + dy; if (a < 0 || a >= M || b < 0 || b >= N || seen[a][b]) continue; seen[a][b] = true; if (A[a][b] < maxH) ans += maxH - A[a][b]; pq.push({ A[a][b], a, b }); } } return ans; } }; -
''' >>> from itertools import pairwise >>> dirs = (-1, 0, 1, 0, -1) >>> pairwise(dirs) <itertools.pairwise object at 0x104dbe470> >>> list(pairwise(dirs)) [(-1, 0), (0, 1), (1, 0), (0, -1)] ''' from heapq import heappush, heappop class Solution: def trapRainWater(self, heightMap: List[List[int]]) -> int: m, n = len(heightMap), len(heightMap[0]) vis = [[False] * n for _ in range(m)] # visited 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: # border enqueue heappush(pq, (heightMap[i][j], i, j)) # default order vis[i][j] = True ans = 0 dirs = (-1, 0, 1, 0, -1) while pq: h, i, j = heappop(pq) for a, b in pairwise(dirs): x, y = i + a, j + b if x >= 0 and x < m and y >= 0 and y < n and not vis[x][y]: ans += max(0, h - heightMap[x][y]) # look for neighbour which is lower than pop result hight vis[x][y] = True heappush(pq, (max(h, heightMap[x][y]), x, y)) return ans ############ class Solution(object): def trapRainWater(self, heightMap): """ :type heightMap: List[List[int]] :rtype: int """ if not heightMap: return 0 h = len(heightMap) w = len(heightMap[0]) ans = 0 heap = [] visited = set() for j in range(w): heapq.heappush(heap, (heightMap[0][j], 0, j)) heapq.heappush(heap, (heightMap[h - 1][j], h - 1, j)) visited |= {(0, j), (h - 1, j)} for i in range(h): heapq.heappush(heap, (heightMap[i][0], i, 0)) heapq.heappush(heap, (heightMap[i][w - 1], i, w - 1)) visited |= {(i, 0), (i, w - 1)} dirs = [(0, -1), (0, 1), (-1, 0), (1, 0)] while heap: height, i, j = heapq.heappop(heap) for di, dj in dirs: ni, nj = i + di, j + dj if 0 <= ni < h and 0 <= nj < w and (ni, nj) not in visited: ans += max(0, height - heightMap[ni][nj]) heapq.heappush(heap, (max(heightMap[ni][nj], height), ni, nj)) # update new hight, max(heightMap[ni][nj], height) visited |= {(ni, nj)} return ans -
func trapRainWater(heightMap [][]int) (ans int) { m, n := len(heightMap), len(heightMap[0]) pq := hp{} vis := make([][]bool, m) for i, row := range heightMap { vis[i] = make([]bool, n) for j, v := range row { if i == 0 || i == m-1 || j == 0 || j == n-1 { heap.Push(&pq, tuple{v, i, j}) vis[i][j] = true } } } dirs := []int{-1, 0, 1, 0, -1} for len(pq) > 0 { p := heap.Pop(&pq).(tuple) for k := 0; k < 4; k++ { x, y := p.i+dirs[k], p.j+dirs[k+1] if x >= 0 && x < m && y >= 0 && y < n && !vis[x][y] { ans += max(0, p.v-heightMap[x][y]) vis[x][y] = true heap.Push(&pq, tuple{max(p.v, heightMap[x][y]), x, y}) } } } return } func max(a, b int) int { if a > b { return a } return b } type tuple struct{ v, i, j int } type hp []tuple func (h hp) Len() int { return len(h) } func (h hp) Less(i, j int) bool { return h[i].v < h[j].v } func (h hp) Swap(i, j int) { h[i], h[j] = h[j], h[i] } func (h *hp) Push(v interface{}) { *h = append(*h, v.(tuple)) } func (h *hp) Pop() interface{} { a := *h; v := a[len(a)-1]; *h = a[:len(a)-1]; return v }