407. 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.
image

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.

image

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

一刷
題解:用priorityQueue, 先把周圍一圈加入queue中,訪問最short的點朋譬,并把short點a的四周b加入queue中冗恨,高度設(shè)置為max(a,b)冠息,如果四周有點比short矮, 加上他們的高度差逗旁。

public class Solution {

    public class 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 trapRainWater(int[][] heights) {
        if (heights == null || heights.length == 0 || heights[0].length == 0)
            return 0;

        PriorityQueue<Cell> queue = new PriorityQueue<>(1, new Comparator<Cell>(){
            public int compare(Cell a, Cell b) {
                return a.height - b.height;
            }
        });
        
        int m = heights.length;
        int n = heights[0].length;
        boolean[][] visited = new boolean[m][n];

        // Initially, add all the Cells which are on borders to the queue.
        for (int i = 0; i < m; i++) {
            visited[i][0] = true;
            visited[i][n - 1] = true;
            queue.offer(new Cell(i, 0, heights[i][0]));
            queue.offer(new Cell(i, n - 1, heights[i][n - 1]));
        }

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

        // from the borders, pick the shortest cell visited and check its neighbors:
        // if the neighbor is shorter, collect the water it can trap and update its height as its height plus the water trapped
       // add all its neighbors to the queue.
        int[][] dirs = new int[][]{{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
        int res = 0;
        while (!queue.isEmpty()) {
            Cell cell = queue.poll();
            for (int[] dir : dirs) {
                int row = cell.row + dir[0];
                int col = cell.col + dir[1];
                if (row >= 0 && row < m-1 && col >= 0 && col < n-1 && !visited[row][col]) {//boundary already check
                    visited[row][col] = true;
                    res += Math.max(0, cell.height - heights[row][col]);
                    queue.offer(new Cell(row, col, Math.max(heights[row][col], cell.height)));
                }
            }
        }
        
        return res;
    }
}
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請聯(lián)系作者
  • 序言:七十年代末蒙具,一起剝皮案震驚了整個濱河市雷绢,隨后出現(xiàn)的幾起案子难咕,更是在濱河造成了極大的恐慌课梳,老刑警劉巖距辆,帶你破解...
    沈念sama閱讀 222,729評論 6 517
  • 序言:濱河連續(xù)發(fā)生了三起死亡事件余佃,死亡現(xiàn)場離奇詭異,居然都是意外死亡跨算,警方通過查閱死者的電腦和手機(jī)爆土,發(fā)現(xiàn)死者居然都...
    沈念sama閱讀 95,226評論 3 399
  • 文/潘曉璐 我一進(jìn)店門,熙熙樓的掌柜王于貴愁眉苦臉地迎上來诸蚕,“玉大人步势,你說我怎么就攤上這事”撤福” “怎么了坏瘩?”我有些...
    開封第一講書人閱讀 169,461評論 0 362
  • 文/不壞的土叔 我叫張陵,是天一觀的道長漠魏。 經(jīng)常有香客問我倔矾,道長,這世上最難降的妖魔是什么柱锹? 我笑而不...
    開封第一講書人閱讀 60,135評論 1 300
  • 正文 為了忘掉前任哪自,我火速辦了婚禮,結(jié)果婚禮上禁熏,老公的妹妹穿的比我還像新娘壤巷。我一直安慰自己,他們只是感情好瞧毙,可當(dāng)我...
    茶點故事閱讀 69,130評論 6 398
  • 文/花漫 我一把揭開白布胧华。 她就那樣靜靜地躺著,像睡著了一般宙彪。 火紅的嫁衣襯著肌膚如雪矩动。 梳的紋絲不亂的頭發(fā)上,一...
    開封第一講書人閱讀 52,736評論 1 312
  • 那天您访,我揣著相機(jī)與錄音铅忿,去河邊找鬼。 笑死灵汪,一個胖子當(dāng)著我的面吹牛檀训,可吹牛的內(nèi)容都是我干的柑潦。 我是一名探鬼主播,決...
    沈念sama閱讀 41,179評論 3 422
  • 文/蒼蘭香墨 我猛地睜開眼峻凫,長吁一口氣:“原來是場噩夢啊……” “哼渗鬼!你這毒婦竟也來了?” 一聲冷哼從身側(cè)響起荧琼,我...
    開封第一講書人閱讀 40,124評論 0 277
  • 序言:老撾萬榮一對情侶失蹤譬胎,失蹤者是張志新(化名)和其女友劉穎,沒想到半個月后命锄,有當(dāng)?shù)厝嗽跇淞掷锇l(fā)現(xiàn)了一具尸體堰乔,經(jīng)...
    沈念sama閱讀 46,657評論 1 320
  • 正文 獨居荒郊野嶺守林人離奇死亡,尸身上長有42處帶血的膿包…… 初始之章·張勛 以下內(nèi)容為張勛視角 年9月15日...
    茶點故事閱讀 38,723評論 3 342
  • 正文 我和宋清朗相戀三年脐恩,在試婚紗的時候發(fā)現(xiàn)自己被綠了镐侯。 大學(xué)時的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片。...
    茶點故事閱讀 40,872評論 1 353
  • 序言:一個原本活蹦亂跳的男人離奇死亡驶冒,死狀恐怖苟翻,靈堂內(nèi)的尸體忽然破棺而出,到底是詐尸還是另有隱情骗污,我是刑警寧澤崇猫,帶...
    沈念sama閱讀 36,533評論 5 351
  • 正文 年R本政府宣布,位于F島的核電站需忿,受9級特大地震影響诅炉,放射性物質(zhì)發(fā)生泄漏。R本人自食惡果不足惜贴谎,卻給世界環(huán)境...
    茶點故事閱讀 42,213評論 3 336
  • 文/蒙蒙 一汞扎、第九天 我趴在偏房一處隱蔽的房頂上張望。 院中可真熱鬧擅这,春花似錦澈魄、人聲如沸。這莊子的主人今日做“春日...
    開封第一講書人閱讀 32,700評論 0 25
  • 文/蒼蘭香墨 我抬頭看了看天上的太陽。三九已至溯香,卻和暖如春鲫构,著一層夾襖步出監(jiān)牢的瞬間,已是汗流浹背玫坛。 一陣腳步聲響...
    開封第一講書人閱讀 33,819評論 1 274
  • 我被黑心中介騙來泰國打工结笨, 沒想到剛下飛機(jī)就差點兒被人妖公主榨干…… 1. 我叫王不留,地道東北人。 一個月前我還...
    沈念sama閱讀 49,304評論 3 379
  • 正文 我出身青樓炕吸,卻偏偏與公主長得像伐憾,于是被迫代替她去往敵國和親。 傳聞我的和親對象是個殘疾皇子赫模,可洞房花燭夜當(dāng)晚...
    茶點故事閱讀 45,876評論 2 361

推薦閱讀更多精彩內(nèi)容