成人国产在线小视频_日韩寡妇人妻调教在线播放_色成人www永久在线观看_2018国产精品久久_亚洲欧美高清在线30p_亚洲少妇综合一区_黄色在线播放国产_亚洲另类技巧小说校园_国产主播xx日韩_a级毛片在线免费

資訊專(zhuān)欄INFORMATION COLUMN

407. Trapping Rain Water II

wenzi / 1076人閱讀

407. Trapping Rain Water II

題目鏈接:
https://leetcode.com/problems...

參考discussion里的解法:
https://discuss.leetcode.com/...

參考博客里的解釋?zhuān)?br>http://www.cnblogs.com/grandy...

public class Solution {
    public int trapRainWater(int[][] heightMap) {
        // base case
        if(heightMap.length == 0 || heightMap[0].length == 0) return 0;
        
        int m = heightMap.length, n = heightMap[0].length;
        // bfs, heap
        boolean[][] visited = new boolean[m][n];
        // add 4 sides first, since 4 side can not store water
        PriorityQueue minHeap = new PriorityQueue<>((m+n), (a, b) -> a.h - b.h);
        // 1st col and last col
        for(int i = 0; i < m; i++) {
            minHeap.offer(new Cell(i, 0, heightMap[i][0]));
            visited[i][0] = true;
            minHeap.offer(new Cell(i, n - 1, heightMap[i][n-1]));
            visited[i][n-1] = true;
        }
        // 1st row and last row
        for(int j = 0; j < n; j++) {
            minHeap.offer(new Cell(0, j, heightMap[0][j]));
            visited[0][j] = true;
            minHeap.offer(new Cell(m-1, j, heightMap[m-1][j]));
            visited[m-1][j] = true;
        }
        // bfs find water
        int res = 0;
        while(!minHeap.isEmpty()) {
            Cell cur = minHeap.poll();
            for(int[] dir : dirs) {
                int nx = cur.x + dir[0], ny = cur.y + dir[1];
                if(nx >= 0 && nx < m && ny >= 0 && ny < n && !visited[nx][ny]) {
                    visited[nx][ny] = true;
                    if(heightMap[nx][ny] < cur.h) res += cur.h - heightMap[nx][ny];
                    minHeap.offer(new Cell(nx, ny, Math.max(cur.h, heightMap[nx][ny])));
                }
            }
        }
        return res;
    }
    
    int[][] dirs = new int[][] {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
}

class Cell {
    int x;
    int y;
    int h;
    Cell(int x, int y, int h) {
        this.x = x;
        this.y = y;
        this.h = h;
    }
}

文章版權(quán)歸作者所有,未經(jīng)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為,您可以聯(lián)系管理員刪除。

轉(zhuǎn)載請(qǐng)注明本文地址:http://systransis.cn/yun/69855.html

相關(guān)文章

  • [Leetcode] Trapping Rain Water 積水問(wèn)題

    摘要:從右向左遍歷時(shí),記錄下上次右邊的峰值,如果左邊一直沒(méi)有比這個(gè)峰值高的,就加上這些差值。難點(diǎn)在于,當(dāng)兩個(gè)指針遍歷到相鄰的峰時(shí),我們要選取較小的那個(gè)峰值來(lái)計(jì)算差值。所以,我們?cè)诒闅v左指針或者右指針之前,要先判斷左右兩個(gè)峰值的大小。 Trapping Rain Water Given n non-negative integers representing an elevation map ...

    caohaoyu 評(píng)論0 收藏0
  • Leetcode[42] Trapping Rain Water

    摘要:復(fù)雜度思路因?yàn)樾钏嗌偃Q于比較短的那塊板的長(zhǎng)度。代碼復(fù)雜度思路考慮說(shuō)明時(shí)候需要計(jì)算蓄水量當(dāng)?shù)臅r(shí)候,需要計(jì)算能儲(chǔ)存的水的多少。每次還需要取出一個(gè)作為中間值。如果則一直向里面壓進(jìn)去值,不需要直接計(jì)算。 Leetcode[42] Trapping Rain Water Given n non-negative integers representing an elevation map ...

    jonh_felix 評(píng)論0 收藏0
  • 42. Trapping Rain Water

    摘要:題目解答左邊比右邊小或者大都可以盛水,所以我們不能直接確定右邊是否會(huì)有一個(gè)柱子比較大,能盛所有現(xiàn)在積攢的水。那么我們就找到中間最大的那個(gè)柱子,把它分成左右兩邊,那么不管從左邊還是右邊都能保證最后可以有最高的柱子在,之前盛的水都是有效的 題目:Given n non-negative integers representing an elevation map where the wid...

    seanlook 評(píng)論0 收藏0
  • [LintCode/LeetCode] Trapping Rain Water [棧和雙指針]

    摘要:一種是利用去找同一層的兩個(gè)邊,不斷累加寄存。雙指針?lè)ǖ乃枷胂日业阶笥覂蛇叺牡谝粋€(gè)峰值作為參照位,然后分別向后向前每一步增加該位與參照位在這一位的差值,加入,直到下一個(gè)峰值,再更新為新的參照位。 Problem Given n non-negative integers representing an elevation map where the width of each bar i...

    bluesky 評(píng)論0 收藏0
  • leetcode42 Trapping Rain Water

    摘要:我先通過(guò)堆棧的方法,找到一個(gè)封閉區(qū)間,該區(qū)間可以盛水,該區(qū)間的右節(jié)點(diǎn)可以作為下一個(gè)封閉區(qū)間的起點(diǎn)。思路三堆棧的聰明使用在這里,堆棧允許我們漸進(jìn)的通過(guò)橫向分割而非之前傳統(tǒng)的縱向分割的方式來(lái)累加計(jì)算盛水量。 題目要求 Given n non-negative integers representing an elevation map where the width of each bar...

    GitCafe 評(píng)論0 收藏0

發(fā)表評(píng)論

0條評(píng)論

最新活動(dòng)
閱讀需要支付1元查看
<