[LintCode/LeetCode] Trapping Rain Water [棧和雙指針]

bluesky 發布于2019-08-14 15:19 / 895人閱讀

摘要：一種是利用去找同一層的兩個邊，不斷累加寄存。雙指針法的思想先找到左右兩邊的第一個峰值作為參照位，然后分別向后向前每一步增加該位與參照位在這一位的差值，加入，直到下一個峰值，再更新為新的參照位。

Problem

Given n non-negative integers representing an elevation map where the width of each bar is 1, compute how much water it is able to trap after raining.

Example

Given [0,1,0,2,1,0,1,3,2,1,2,1], return 6.

Note

有兩種方法。一種是利用Stack去找同一層的兩個邊，不斷累加寄存。如[2, 1, 0, 1, 2]，2入棧，1入棧，0入棧，下一個1大于棧頂元素0，則計算此處的雨水量加入res，此過程中0從棧中彈出，1入棧，到下一個2，先彈出1，由于之前還有一個1在棧中，所以計算時高度的因數相減為0，雨水量為0，res無變化，繼續pop出棧中的元素，也就是之前的1，此時stack中仍有元素2，說明左邊還有邊，繼續計算底層高度為1，兩個值為2的邊之間的水量，加入res。
雙指針法的思想：先找到左右兩邊的第一個峰值作為參照位，然后分別向后（向前）每一步增加該位與參照位在這一位的差值，加入sum，直到下一個峰值，再更新為新的參照位。這里有一個需要注意的地方，為什么要先計算左右兩個峰值中較小的那個呢？因為在兩個指針逼近中間組成最后一個積水區間時，要用較短邊計算。

Solution

1. Stack

public class Solution {
    public int trapRainWater(int[] A) {
        Stack stack = new Stack();
        int res = 0;
        for (int i = 0; i < A.length; i++) {
            if (stack.isEmpty() || A[i] < A[stack.peek()]) stack.push(i);
            else {
                while (!stack.isEmpty() && A[i] > A[stack.peek()]) {
                    int pre = stack.pop();
                    if (!stack.isEmpty()) {
                        res += (Math.min(A[i], A[stack.peek()]) - A[pre]) * (i - stack.peek() - 1);
                    }
                }
                stack.push(i);
            }
        }
        return res;
    }
}

2. Two-Pointer

public class Solution {
    public int trap(int[] A) {
        int left = 0, right = A.length-1, res = 0;
        while (left < right && A[left] < A[left+1]) left++;
        while (left < right && A[right] < A[right-1]) right--;
        while (left < right) {
            int leftmost = A[left], rightmost = A[right];
            if (leftmost < rightmost) {
                while (left < right && A[++left] < leftmost) res += leftmost - A[left];
            }
            else {
                while (left < right && A[--right] < rightmost) res += rightmost - A[right];
            }
        }
        return res;
    }
}

雙指針法update: 2018-3

public class Solution {
    public int trap(int[] A) {
        if (A == null || A.length < 3) return 0;
        
        //set left/right pointers
        int l = 0, r = A.length-1;
        
        //find the first left/right peaks as left/right bounds
        while (l < r && A[l] <= A[l+1]) l++;
        while (l < r && A[r] <= A[r-1]) r--;
        
        //output
        int trappedWater = 0;
        
        //implementation
        while (l < r) {
            
            int left = A[l];
            int right = A[r];
             
            //when you have a higher RIGHT bound...
            if (left <= right) {

             //when "l" is highest left bound
             //it"s safe to add trapped water RIGHTward
             while (l < r && left >= A[l+1]) {
                 l++;
                 trappedWater += left - A[l];
             }

             //when left pointer "l" found "l+1" a higher left bound
             //reset the left bound
             l++;
            } 

            
            //when you have a higher LEFT bound...
            else {

             //when "r" is highest right bound
             //it"s safe to add trapped water LEFTward
             while (l < r && right >= A[r-1]) {
                 r--;
                 trappedWater += right - A[r];
             }

             //when right pointer "r" found "r-1" a higher right bound
             //reset the right bound
             r--;
            }
        }
        
        return trappedWater;
    }
}

GPU云服務器云服務器 Rain Trapping water java單例和雙例

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

轉載請注明本文地址：http://specialneedsforspecialkids.com/yun/65612.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
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
407. Trapping Rain Water II

407. Trapping Rain Water II 題目鏈接：https://leetcode.com/problems... 參考discussion里的解法：https://discuss.leetcode.com/... 參考博客里的解釋：http://www.cnblogs.com/grandy... public class Solution { public int tra...

wenzi 2019-08-16 10:28 評論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