美文网首页
Trapping Water II

Trapping Water II

作者: Star_C | 来源:发表于2018-03-01 21:41 被阅读0次

    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;
        }
    }
    

    相关文章

      网友评论

          本文标题:Trapping Water II

          本文链接:https://www.haomeiwen.com/subject/tkivxftx.html