Java实现 LeetCode 407 接雨水 II（二）

407. 接雨水 II

给定一个 m x n 的矩阵，其中的值均为正整数，代表二维高度图每个单元的高度，请计算图中形状最多能接多少体积的雨水。

说明:

m 和 n 都是小于110的整数。每一个单位的高度都大于 0 且小于 20000。

示例：

给出如下 3x6 的高度图:

[

[1,4,3,1,3,2],

[3,2,1,3,2,4],

[2,3,3,2,3,1]

]

返回 4。

如上图所示，这是下雨前的高度图[[1,4,3,1,3,2],[3,2,1,3,2,4],[2,3,3,2,3,1]] 的状态。

下雨后，雨水将会被存储在这些方块中。总的接雨水量是4。

class Solution {

    private static 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;

		}

		@Override

		public int compareTo(Cell o) {

			return this.height - o.height;

		}

	}

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

		if (heightMap.length <= 1 || heightMap[0].length <= 1) {// <=1行或每行<=1个元素,没法3维接水

			return 0;

		}

		boolean[][] visited = new boolean[heightMap.length][heightMap[0].length];// 默认被初始化为false

		PriorityQueue<Cell> queue = new PriorityQueue<Cell>();// 小堆

		int waterTraped = 0;

		// 1.初始化把最外围圈入队

		for (int j = 0; j < heightMap[0].length; j++) {// 上下行

			queue.add(new Cell(0, j, heightMap[0][j]));

			queue.add(new Cell(heightMap.length - 1, j,

					heightMap[heightMap.length - 1][j]));

			visited[0][j] = true;

			visited[heightMap.length - 1][j] = true;

		}

		for (int i = 1; i < heightMap.length - 1; i++) {// 左右列，notice顶点不要重复添加，因此...from

														// 1 to length-2

			queue.add(new Cell(i, 0, heightMap[i][0]));

			queue.add(new Cell(i, heightMap[0].length - 1,

					heightMap[i][heightMap[0].length - 1]));

			visited[i][0] = true;

			visited[i][heightMap[0].length - 1] = true;

		}

		// 2.逐点收集雨水--通过优先队列找短板

		Cell lowestWall;// 最矮的墙

		int row, col;

		int[][] direction = { { 1, 0 }, { 0, 1 }, { -1, 0 }, { 0, -1 } };// 下右上左四个方向

		while (!queue.isEmpty()) {

			lowestWall = queue.poll();

			for (int i = 0; i < 4; i++) {

				row = lowestWall.row + direction[i][0];

				col = lowestWall.col + direction[i][1];

				if (row < 0 || row > heightMap.length - 1 || col < 0

						|| col > heightMap[0].length - 1

						|| visited[row][col] == true) {// 越界检查+已经计算检查

					continue;

				}

				waterTraped += Math.max(

						lowestWall.height - heightMap[row][col], 0);// 当前单元格高<lowestWall高，则可以接至lowestWall.height,否则不能接水

				queue.add(new Cell(row, col, Math.max(lowestWall.height,

						heightMap[row][col])));// key point.加入队列成为新墙，墙高取大的

				visited[row][col] = true;

			}

		}

		return waterTraped;

	}

}

Java实现 LeetCode 407 接雨水 II（二）的相关教程结束。