Java Solution with PriorityQueue


  • 1
    M
    public class Solution {
        private class Point implements Comparable<Point>{
            int x, y;
            int h;
            public Point(int x, int y, int h) {
                this.x = x;
                this.y = y;
                this.h = h;
            }
            @Override
            public int compareTo(Point b) {
                return this.h - b.h;
            }
        }
        public int trapRainWater(int[][] heightMap) {
            if (heightMap == null || heightMap.length == 0) return 0;
            int m = heightMap.length, n = heightMap[0].length;
            Queue<Point> q = new PriorityQueue<>();
            boolean[][] vis = new boolean[m][n];
            for (int i = 0; i < m; ++i) {
                q.offer(new Point(i, 0, heightMap[i][0]));
                q.offer(new Point(i, n - 1, heightMap[i][n - 1]));
                vis[i][0] = vis[i][n - 1] = true;
            }
            for (int j = 1; j < n - 1; ++j) {
                q.offer(new Point(0, j, heightMap[0][j]));
                q.offer(new Point(m - 1, j, heightMap[m - 1][j]));
                vis[0][j] = vis[m - 1][j] = true;
            }
            int sum = 0;
            int max = 0;
            int[] dx = {-1, 1, 0, 0}, dy = {0, 0, -1, 1};
            while (!q.isEmpty()) {
                Point p = q.poll();
                max = Math.max(max, p.h);
                sum += max - heightMap[p.x][p.y];
                for (int k = 0; k < dx.length; ++k) {
                    int x = p.x + dx[k], y = p.y + dy[k];
                    if (x >= 0 && x < m && y >= 0 && y < n && !vis[x][y]) {
                        q.offer(new Point(x, y, Math.max(max, heightMap[x][y])));
                        vis[x][y] = true;
                    }
                }
            }
            return sum;
        }
    }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.