Givenn_x_m_non-negative integers representing an elevation map 2d where the area of each cell is_1_x_1, compute how much water it is able to trap after raining.

Have you met this question in a real interview?

Yes

Example

Given5*4matrix

[12,13,0,12]
[13,4,13,12]
[13,8,10,12]
[12,13,12,12]
[13,13,13,13]

return14.

思路

从外想内灌水，当前外围内最矮的柱子决定水位（queue中），pop出的点一定是所有外围点中最小的，所以说只要加入的点比它小，就可以看做是水位差来存水。

用priority queue(heap) 来维护一个最小堆，从外围想内bfs

class Point {
    int i;
    int j;
    int val;
    public Point(int i, int j, int val) {
        this.i = i;
        this.j = j;
        this.val = val;
    }
}
public class Solution {
    /*
     * @param heights: a matrix of integers
     * @return: an integer
     */

    private int[] dx = {0,0, 1, -1};
    private int[] dy = {1,-1,0, 0};
    public int trapRainWater(int[][] heights) {
        // write your code here
        if (heights == null || heights.length < 3 || heights[0] == null || heights[0].length == 0) {
            return 0;
        }

        int ans = 0;
        int n = heights.length;
        int m = heights[0].length;
        //min heap
        PriorityQueue<Point> pq = new PriorityQueue<Point>(heights.length, new Comparator<Point>(){
           public int compare(Point a, Point b) {
               return a.val - b.val;
           } 
        });

        for (int i = 0; i < n; i++) {
            pq.offer(new Point(i, 0, heights[i][0]));
            heights[i][0] = -1;
            pq.offer(new Point(i, m - 1, heights[i][m - 1]));
            heights[i][m - 1] = -1;
        }
        for (int i = 0; i < m; i++) {
            pq.offer(new Point(0, i, heights[0][i]));
            heights[0][i] = -1;
            pq.offer(new Point(n - 1, i, heights[n - 1][i]));
            heights[n - 1][i] = -1;
        }

        int waterLevel = 0;
        while (!pq.isEmpty()) {
            Point cur = pq.poll();
            for (int i = 0; i < 4; i++) {
                int new_i = cur.i + dx[i];
                int new_j = cur.j + dy[i];
                if (new_i < 0 || new_i >= n || new_j < 0 || new_j >= m || heights[new_i][new_j] == -1) {
                    continue;
                }
                pq.offer(new Point(new_i, new_j, Math.max(heights[new_i][new_j], cur.val)));
                //ans += Math.max(0, cur.val - heights[new_i][new_j]);
                heights[new_i][new_j] = -1;
            }
        }
        return ans;
    }
}