407. Trapping Rain Water II

wenzi 發布于2019-08-16 10:28 / 1067人閱讀

407. Trapping Rain Water II

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

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

參考博客里的解釋：
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;
    }
}

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://specialneedsforspecialkids.com/yun/69855.html

[Leetcode] Trapping Rain Water 積水問題

摘要：從右向左遍歷時，記錄下上次右邊的峰值，如果左邊一直沒有比這個峰值高的，就加上這些差值。難點在于，當兩個指針遍歷到相鄰的峰時，我們要選取較小的那個峰值來計算差值。所以，我們在遍歷左指針或者右指針之前，要先判斷左右兩個峰值的大小。 Trapping Rain Water Given n non-negative integers representing an elevation map ...

caohaoyu 2019-08-14 12:29 評論0 收藏0
Leetcode[42] Trapping Rain Water

摘要：復雜度思路因為蓄水多少取決于比較短的那塊板的長度。代碼復雜度思路考慮說明時候需要計算蓄水量當的時候，需要計算能儲存的水的多少。每次還需要取出一個作為中間值。如果則一直向里面壓進去值，不需要直接計算。 Leetcode[42] Trapping Rain Water Given n non-negative integers representing an elevation map ...

jonh_felix 2019-08-14 15:03 評論0 收藏0
42. Trapping Rain Water

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

seanlook 2019-08-14 16:31 評論0 收藏0
[LintCode/LeetCode] Trapping Rain Water [棧和雙指針]

摘要：一種是利用去找同一層的兩個邊，不斷累加寄存。雙指針法的思想先找到左右兩邊的第一個峰值作為參照位，然后分別向后向前每一步增加該位與參照位在這一位的差值，加入，直到下一個峰值，再更新為新的參照位。 Problem Given n non-negative integers representing an elevation map where the width of each bar i...

bluesky 2019-08-14 15:19 評論0 收藏0
leetcode42 Trapping Rain Water

摘要：我先通過堆棧的方法，找到一個封閉區間，該區間可以盛水，該區間的右節點可以作為下一個封閉區間的起點。思路三堆棧的聰明使用在這里，堆棧允許我們漸進的通過橫向分割而非之前傳統的縱向分割的方式來累加計算盛水量。題目要求 Given n non-negative integers representing an elevation map where the width of each bar...

GitCafe 2019-08-16 10:37 評論0 收藏0