407. Trapping Rain Water II _Water

满堂花醉三千客，一剑霜寒十四州。这篇文章主要讲述407. Trapping Rain Water II相关的知识，希望能为你提供帮助。

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 are trapped between the blocks. The total volume of water trapped is 4.

Analysis, 根据木桶原理，先找外围最矮的bar，里边如果有bar比它还矮，一定能存水（因为四周所有的bar都比它高）
注意还可能存更多的水，因为往里面，很可能cell高度变化。所以要把BFS中间遇到的高的bar都存进queue，随着水平面提升，提升到这些bar的高度，看能不能有凹槽存更多的水
44-45行逻辑就是
if (height[row][col] < cur) {
res += cur.height- height[row][col];
queue.offer(new Cell(row, col, cur.height));
【407. Trapping Rain Water II】}
else {
queue.offer(new Cell(row, col, height[row][col]));
}

public class Solution {public class Cell { int row; int col; int height; public Cell(int row, int col, int height) { this.row = row; this.col = col; this.height = height; } }public int trapRainWater(int[][] heights) { if (heights == null || heights.length == 0 || heights[0].length == 0) return 0; PriorityQueue< Cell> queue = new PriorityQueue< > (1, new Comparator< Cell> (){ public int compare(Cell a, Cell b) { return a.height - b.height; } }); int m = heights.length; int n = heights[0].length; boolean[][] visited = new boolean[m][n]; // Initially, add all the Cells which are on borders to the queue. for (int i = 0; i < m; i++) { visited[i][0] = true; visited[i][n - 1] = true; queue.offer(new Cell(i, 0, heights[i][0])); queue.offer(new Cell(i, n - 1, heights[i][n - 1])); }for (int i = 0; i < n; i++) { visited[0][i] = true; visited[m - 1][i] = true; queue.offer(new Cell(0, i, heights[0][i])); queue.offer(new Cell(m - 1, i, heights[m - 1][i])); }// from the borders, pick the shortest cell visited and check its neighbors: // if the neighbor is shorter, collect the water it can trap and update its height as its height plus the water trapped // add all its neighbors to the queue. int[][] dirs = new int[][]{{-1, 0}, {1, 0}, {0, -1}, {0, 1}}; int res = 0; while (!queue.isEmpty()) { Cell cell = queue.poll(); for (int[] dir : dirs) { int row = cell.row + dir[0]; int col = cell.col + dir[1]; if (row > = 0 & & row < m & & col > = 0 & & col < n & & !visited[row][col]) { visited[row][col] = true; res += Math.max(0, cell.height - heights[row][col]); queue.offer(new Cell(row, col, Math.max(heights[row][col], cell.height))); } } }return res; } }