🌕🌕 407. 接雨水 II

难度: 🌕🌕

问题描述

---

解法

class Solution {
    public int trapRainWater(int[][] heightMap) {
        // 思路：
        // 优先队列
        // 初始将四条边界的元素加入优先队列，每次取出最小的元素
        // 判断能否往四个方向注水
        // 利用数组去重
        int row = heightMap.length;
        int col = heightMap[0].length;
        if(row <= 2 && col <= 2) {
            return 0;
        }
        int res = 0;
        int[][] arr = new int[][] {{0, -1}, {0, 1}, {-1, 0}, {1, 0}};
        boolean[][] visit = new boolean[row][col];
        PriorityQueue<int[]> queue = new PriorityQueue<>((a, b) -> {
            return a[2] - b[2]; // 根据高度值创建小根堆
        }); // (x, y, height)

        // 添加边界元素
        for(int j = 0; j < col; j ++) {
            // 首行
            queue.offer(new int[] {0, j, heightMap[0][j]});
            visit[0][j] = true;
        }
        for(int j = 0; j < col; j ++) {
            // 尾行
            queue.offer(new int[] {row - 1, j, heightMap[row - 1][j]});
            visit[row - 1][j] = true;
        }
        for(int i = 1; i < row - 1; i ++) {
            // 左行
            queue.offer(new int[] {i, 0, heightMap[i][0]});
            visit[i][0] = true;
        }
        for(int i = 1; i < row - 1; i ++) {
            // 右行
            queue.offer(new int[] {i, col - 1, heightMap[i][col - 1]});
            visit[i][col - 1] = true;
        }
        // 循环
        while(!queue.isEmpty()) {
            int[] cur = queue.poll();
            // 往四个方向遍历，判断能否注水
            for(int[] j: arr) {
                int nx = cur[0] + j[0];
                int ny = cur[1] + j[1];
                if(nx >= 0 && nx < row && ny >= 0 && ny < col && !visit[nx][ny]) {
                    // 判断能否注水
                    if(heightMap[nx][ny] < cur[2]) {
                        res += cur[2] - heightMap[nx][ny];
                        queue.offer(new int[] {nx, ny, cur[2]});
                    } else {
                        queue.offer(new int[] {nx, ny, heightMap[nx][ny]});
                    }
                    visit[nx][ny] = true;
                }
            }
        }
        return res;
    }
}

---

输出