Leetcode 407. Trapping Rain Water II

Description

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.

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.
img

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.

img

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

Constraints:

  • 1 <= m, n <= 110
  • 0 <= heightMap[i][j] <= 20000

Solution

这个题是42.Trapping Rain Water的3D版了,42题用的双指针左右逼近,每次最小的那一端向中间移动,本来我以为这道题也是一行行的双指针逼近,还是too young了。

其实也应该想到,二维空间中,应该是四个方向同时逼近了。

本题的解法主要利用小根堆(Java中的PriorityQueue),自动将最矮的方法放在根结点上,时间复杂度为O(logn)。

  1. 首先将数组的四个边界的方块入队,从最矮的方块向邻近方块开始做BFS。(为什么是最矮呢?因为如果是从最高方块开始,你就算碰到了矮方块,你也无法判断它能存多少水,因为每个方块的存水量由边界中最矮的那个决定)
  2. 如果邻近方块的高度低于当前方块,则直接res += cell.height - neighbor.height。并记录作为的边界的最大值。
  3. 循环往复的遍历

代码如下:

class Solution {

    class Cell implements Comparable<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 compareTo (Cell cell) {
            return this.height - cell.height;
        }
    }

    public int trapRainWater(int[][] heightMap) {

        if (heights == null || heights.length == 0 || heights[0].length == 0)
            return 0;

        int m = heightMap.length;
        int n = heightMap[0].length;

        PriorityQueue<Cell> q = new PriorityQueue<>();
        boolean[][] visited = new boolean[m][n];

        for (int i = 0; i < m; i++) {
            visited[i][0] = true;
            visited[i][n - 1] = true;
            q.offer(new Cell(i, 0, heightMap[i][0]));
            q.offer(new Cell(i, n - 1, heightMap[i][n - 1]));
        }

        for (int j = 1; j < n - 1; j++) {
            visited[0][j] = true;
            visited[m - 1][j] = true;
            q.offer(new Cell(0, j, heightMap[0][j]));
            q.offer(new Cell(m - 1, j, heightMap[m - 1][j]));
        }

        int[] direction = new int[]{0, 1, 0, -1, 0};
        int res = 0;

        while (!q.isEmpty()) {
              Cell cell = q.poll();
              for (int i = 0; i < 4; i++) {
                  int r = cell.row + direction[i];
                  int c = cell.col + direction[i + 1];
                  if (r >= 0 && r < m && c >= 0 && c < n && !visited[r][c]) {
                      res += Math.max(0, cell.height - heightMap[r][c]);
                      // 入队的结点的高度是边界的最大高度
                      q.offer(new Cell(r, c, Math.max(cell.height, heightMap[r][c])));
                      visited[r][c] = true;
                  }
              }
        }
        return res;
    }
}

Discuss中有个很好的演示视频

暂无评论

发表评论

电子邮件地址不会被公开。 必填项已用*标注

浙ICP备19002997号