力扣 407. 接雨水 II

力扣 407. 接雨水 II

题目链接

首先要知道一点：这个矩阵的边缘是无法接水的，如果我们设 w a t e r [ i ] [ j ] water[i][j] water[i][j] 是 ( i , j ) (i, j) (i,j) 点水的高度，那么对于矩阵边缘来所， w a t e r [ i ] [ j ] = h e i g h t M a p [ i ] [ j ] water[i][j]=heightMap[i][j] water[i][j]=heightMap[i][j]，接到水的体积就是 w a t e r [ i ] [ j ] − h e i g h t M a p [ i ] [ j ] = 0 water[i][j]-heightMap[i][j]=0 water[i][j]−heightMap[i][j]=0

那么根据木桶效应，水的高度取决于最短的那一个木板。我们把这个矩阵看成一个桶，矩阵的边缘就是木板，我们找出最短的那一个，设位置是 ( x , y ) (x,y) (x,y)，那么对于它相邻的点 ( n x , n y ) (nx,ny) (nx,ny)，接到水的高度就是 w a t e r [ n x ] [ n y ] = M a x ( h e i g h t M a p [ n x ] [ n y ] , w a t e r [ x ] [ y ] ) water[nx][ny]=Max(heightMap[nx][ny],water[x][y]) water[nx][ny]=Max(heightMap[nx][ny],water[x][y])

计算完 ( n x , n y ) (nx,ny) (nx,ny) 水的高度后，该点又可以看作是木桶的一块木板，而 ( x , y ) (x,y) (x,y) 就可以不计算在木板内了。此时就想到可以使用优先队列计算。

做这道题多少看了看力扣的官方题解（因为不会用 java 的优先队列。。。

class Solution {
    public int trapRainWater(int[][] heightMap) {
        int ans = 0;
        int m = heightMap.length;
        int n = heightMap[0].length;
        int[][] water = new int[m][n];
        boolean[][] vis = new boolean[m][n];
        PriorityQueue pQue = new PriorityQueue<>((o1, o2) -> o1[1] - o2[1]);
        for (int i=0;i 0 && nx < m && ny > 0 && ny < n && !vis[nx][ny]) {
                    water[nx][ny] = Math.max(heightMap[nx][ny], water[x][y]);
                    pQue.add(new int[]{nx * n + ny, water[nx][ny]});
                    ans += water[nx][ny] - heightMap[nx][ny];
                    vis[nx][ny] = true;
                }
            }
        }
        return ans;
    }
}