LeetCode关于接雨水的问题

关于我的 Leetcode 题目解答，代码前往 Github：https://github.com/chenxiangcyr/leetcode-answers

---

LeetCode题目：42. Trapping Rain Water
Given n non-negative integers representing an elevation map where the width of each bar is 1, compute how much water it is able to trap after raining.

For example,
Given [0,1,0,2,1,0,1,3,2,1,2,1], return 6.

Trapping Rain Water

The above elevation map is represented by array [0,1,0,2,1,0,1,3,2,1,2,1]. In this case, 6 units of rain water (blue section) are being trapped.

class Solution {
    public int trap(int[] height) {
        int ans = 0;
        int current = 0;
        
        // 存储的是idx
        Stack<Integer> st = new Stack<Integer>();
        
        while (current < height.length) {
            while (!st.isEmpty() && height[current] > height[st.peek()]) {
                int top = st.pop();
                
                if (st.empty())
                    break;
                
                int distance = current - st.peek() - 1;
                int bounded_height = Math.min(height[current], height[st.peek()]);
                
                ans += distance * (bounded_height - height[top]);
            }
            
            st.push(current);
            current++;
        }
        return ans;
    }
}

LeetCode题目：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.

Trapping Rain Water II

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.

Trapping Rain Water II

After the rain, water is trapped between the blocks. The total volume of water trapped is 4.

参考 https://github.com/shawnfan/LintCode/blob/master/Java/Trapping Rain Water II.java

class Solution {
    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，即一个最小堆
        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];

        // 将四个边界加入
        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;
                    
                    if(cell.height > heights[row][col]) {
                        res = res + cell.height - heights[row][col];
                        
                        queue.offer(new Cell(row, col, cell.height));
                    } else {
                        queue.offer(new Cell(row, col, heights[row][col]));
                    }
                }
            }
        }
        
        return res;
    }
}