Question quoted from lintcode
Given n x m non-negative integers representing an elevation map 2d where the area of each cell is 1 x 1, compute how much water it is able to trap after raining.
img
Example:
Given 5*4 matrix
[12,13,0,12]
[13,4,13,12]
[13,8,10,12]
[12,13,12,12]
[13,13,13,13]
return 14.
Idea
這題用母語都不容易把代碼講明白。
題目大意就是要向這些柱子組成的矩陣澆水,問一共能灌多少水。題目假設柱子之間沒有間隙。
我先講講我自己的思路吧。
思路說起來好像挺簡單的,就是從最外層開始澆水,層層往矩陣內部澆。
一圈柱子圍起來,它的可灌水高度,是由最低的一根柱子決定的。直觀上,你要把最外層的圈找到,得到可灌水高度(最低柱), 然後嘗試向圈內灌水,然後,往圈子內部找下一個更高的封閉圈,往上澆水,再找下一個封閉圈……
實際上代碼直接實現這個思路非常麻煩。把所有的封閉圈辨識出來就夠你喝一壺的。以下介紹另一種思路。非原創,代碼如有類同,實屬抄襲。
代碼實現的思路
我們不考慮可灌水量,因爲每根柱子都不一樣,我們考慮灌水後的高度。這個高度對於每一個柱子圍成的圈來說, 每根內柱都是一樣,統一的,除非柱子超出了水面。
定義一個數據結構Cell, 裏面包含了柱子的位置,和柱子的灌水後高度。
維護一個最小優先隊列,先把矩陣4條邊的柱子和他們的灌水後高度打包成Cell, 全部送進隊列,也就是首行尾行和首列尾列,對於這4條邊來說,每一根柱子的灌水後的高度應該是自身高度 + 0單位的水
也就是柱子高度本身,因爲最外層邊柱不能夠被灌水。
然後不停執行隊列的出列操作。
推論1
這裏必須理解的是,由於最外圈已經首先訪問過了,並且全部排進了隊列,所以接下來出列的每一根柱子,還有他們的未訪問的相鄰柱子,都必然在不可能在最外圈以外。只能在最外圈或最外圈以內。
最小優先隊列第一次出列的,必然是邊柱最矮的一根。
檢查其前後左右而且"沒有訪問過"的相鄰柱子,嘗試向其灌水。如果鄰居比它的灌水後高度還矮,那就可以灌水。給鄰居柱子灌水以後,你可以把鄰居看成一條邊柱,它的高度爲“鄰居自身高度 + 灌上去的水”,也就是出列的柱子本身的高度,把這根虛擬的邊柱加進隊列,以便未來會對其鄰居進行灌水。如果鄰居比出列柱子的灌水後高度還要高,那這根柱子已經浮出水面了,把鄰居當作邊柱,直接加進隊列。
所以這裏對於每一根柱子的遍歷順序是這樣的:首先是最外包圍的圈,然後逐漸向內蔓延(前後左右的鄰居柱子)直到把整個矩陣都訪問一遍。
推論2
由於永遠是最矮的柱子先出列,所以可以確定的是,遍歷過程中,圍圈的最低柱子和它的鄰居總是會被最先灌水。
這個灌水的順序和現實物理是相悖的。這裏是理解代碼最困難的地方,一點也不直觀。
Code
class Cell {
public final int rowNum;
public final int colNum;
// 注意,這裏表示灌水後的高度! 如果這個位置不能被灌水,就會和柱子高度一樣,相當於加了0個單位的水
public final int waterLevel;
Cell(int rowNum, int colNum, int level) {
this.rowNum = rowNum;
this.colNum = colNum;
this.waterLevel = level;
}
}
public class Solution {
/*
* @param heights: a matrix of integers
* @return: an integer
*/
public int trapRainWater(int[][] heights) {
// write your code here
if (heights.length == 0) return 0;
// 創建一個最小優先隊列,語法挺麻煩的
PriorityQueue<Cell> boundaryCells = new PriorityQueue<Cell>((c1, c2) -> {
if (c1.waterLevel == c2.waterLevel) return 0;
if (c1.waterLevel > c2.waterLevel) return 1;
return -1;
});
int rowLen = heights.length;
int colLen = heights[0].length;
// initialize the variable
boolean[][] visited = new boolean[rowLen][colLen];
for (int i = 0; i < rowLen; i++) {
for (int j = 0; j < colLen; j++) {
visited[i][j] = false;
}
}
// 把首行,尾行,首列,尾列的柱子都加進隊列
int firstRow = 0;
int firstColumn = 0;
int lastRow = rowLen - 1;
int lastColumn = colLen - 1;
// first column and last column 首列尾列
for(int row_i = 0; row_i < rowLen; row_i++) {
boundaryCells.add(new Cell(row_i, firstColumn, heights[row_i][firstColumn]));
boundaryCells.add(new Cell(row_i, lastColumn, heights[row_i][lastColumn]));
visited[row_i][firstColumn] = true;
visited[row_i][lastColumn] = true;
}
// first row and last row 首行尾行
for(int column_i = 1; column_i < colLen - 1; column_i++) {
boundaryCells.add(new Cell(firstRow, column_i, heights[firstRow][column_i]));
boundaryCells.add(new Cell(lastRow, column_i, heights[lastRow][column_i]));
visited[firstRow][column_i] = true;
visited[lastRow][column_i] = true;
}
int water = 0;
int[][] moves = { {1, 0}, {-1, 0}, {0, 1}, {0, -1}, };
int row = 0; int col = 1;
while(!boundaryCells.isEmpty()) {
// start from the cell with least waterLevel 出列的順序一定是最矮的先出
Cell current = boundaryCells.poll();
// visit its 4 neighbors
for(int[] move : moves) {
int rowPos = current.rowNum + move[row];
int colPos = current.colNum + move[col];
// make sure the neighbor is valid index
// and is never visited before
boolean valid = (0 <= rowPos && rowPos < rowLen) &&
(0 <= colPos && colPos < colLen) &&
visited[rowPos][colPos] == false;
if (valid) {
visited[rowPos][colPos] = true;
if (current.waterLevel > heights[rowPos][colPos]) {
water += current.waterLevel - heights[rowPos][colPos];
// 這是一根虛擬的邊柱,其高度 = 真實柱子高度 + 灌上的水, 也就是和當前柱子的灌水後高度一樣的
boundaryCells.add(new Cell(rowPos, colPos, current.waterLevel));
} else {
// 這根柱子浮出水面了,有可能成爲下一個"更高的內圈"的邊柱,這根柱子越高,就越排到後面才出列。
boundaryCells.add(new Cell(rowPos, colPos, heights[rowPos][colPos]));
}
}
}
}
return water;
}
}
网友评论