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

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.

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

神仙题。能够想出来用优先队列和广度优先遍历结合的都是大佬。希望所有看到这道题目的可以在文章回复里面分享一下写这题的思路。在下面我就粘贴一下根据油管上的思路写成的 JAVA 解答。

思路和代码

思路的动画

public int trapRainWater(int[][] heightMap) {if (heightMap == null || heightMap.length <= 2 || heightMap[0].length <= 2) {return 0;}
        int rowCount = heightMap.length;
        int columnCount = heightMap[0].length;
        boolean[][] visited = new boolean[rowCount][columnCount];
        PriorityQueue<Position> queue = new PriorityQueue<>();
        for (int i = 0 ; i < rowCount ; i++) {visited[i][0] = true;
            queue.offer(new Position(i, 0, heightMap[i][0]));
            visited[i][columnCount-1] = true;
            queue.offer(new Position(i, columnCount-1, heightMap[i][columnCount-1]));
        }

        for (int i = 1 ; i < columnCount ; i++) {visited[0][i] = true;
            queue.offer(new Position(0, i, heightMap[0][i]));
            visited[rowCount-1][i] = true;
            queue.offer(new Position(rowCount-1, i, heightMap[rowCount-1][i]));
        }

        int water = 0;
        int max = 0;
        while (!queue.isEmpty()) {Position position = queue.poll();
            if (position.value > max) {max = position.value;}else {water += max - position.value;}
            int rowIndex = position.rowIndex;
            int columnIndex = position.columnIndex;
            if (rowIndex > 0 && !visited[rowIndex-1][columnIndex]) {queue.offer(new Position(rowIndex-1, columnIndex, heightMap[rowIndex-1][columnIndex]));
                visited[rowIndex-1][columnIndex] = true;
            }
            if (rowIndex < rowCount-1 && !visited[rowIndex+1][columnIndex]) {queue.offer(new Position(rowIndex+1, columnIndex, heightMap[rowIndex+1][columnIndex]));
                visited[rowIndex+1][columnIndex] = true;
            }
            if (columnIndex > 0 && !visited[rowIndex][columnIndex-1]) {queue.offer(new Position(rowIndex, columnIndex-1, heightMap[rowIndex][columnIndex-1]));
                visited[rowIndex][columnIndex-1] = true;
            }
            if (columnIndex < columnCount - 1 && !visited[rowIndex][columnIndex+1]) {queue.offer(new Position(rowIndex, columnIndex+1, heightMap[rowIndex][columnIndex+1]));
                visited[rowIndex][columnIndex+1] = true;
            }
        }
        return water;
    }

    public static class Position implements Comparable<Position> {
        int rowIndex;
        int columnIndex;
        int value;

        Position(int rowIndex, int columnIndex, int value) {
            this.rowIndex = rowIndex;
            this.columnIndex = columnIndex;
            this.value = value;
        }

        @Override
        public int compareTo(Position o) {return this.value - o.value;}

    }