摘要：我先通過堆棧的方法，找到一個封閉區間，該區間可以盛水，該區間的右節點可以作為下一個封閉區間的起點。思路三堆棧的聰明使用在這里，堆棧允許我們漸進的通過橫向分割而非之前傳統的縱向分割的方式來累加計算盛水量。

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.

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

假設這些是一些間隔的木板，問最多能夠裝多少水。也就是一個區域性的短板問題。其實一個區間能夠乘的最大水量，取決于它的左右最近且最高的木板的長度。當然除了通過多個區間的和來計算總體的盛水量，還可以通過橫向的劃分來計算盛水量。這些將在接下來中的代碼一一分析。官方也提供了一些答案，這里將給出相應的java實現的版本。

這里先講一講我在拿到這個題目時候的思路。我先通過堆棧的方法，找到一個封閉區間，該區間可以盛水，該區間的右節點可以作為下一個封閉區間的起點。這種方法思路非常直接，但是并不是高效的計算機思維。
堆棧的方法如下：

    //使用堆棧，分別存儲值和下標
    public int trap(int[] height) {
        int length = height.length;
        if(length<=2){
            return 0;
        }
        
        Stack s = new Stack();
        Stack index = new Stack();
        s.push(0);
        index.push(1);
        
        int leftMost = 0;
        int result = 0;
        for(int i = 0 ; i= leftMost){
                while(!s.isEmpty()){
                    result += (leftMost - s.pop()) * index.pop();
                }
                s.push(currentVal);
                index.push(1);
                leftMost = currentVal;
            }else{
                //如果當前值比最左值小，則說明該盛水區間仍然沒到最右點
                int count = 1;
                //將所有比當前值小的區間填滿，并將水平區間的個數插入棧中
                while(currentVal > s.peek()){
                    count += index.peek();
                    result += (currentVal - s.pop()) * index.pop();
                }
                s.push(currentVal);
                index.push(count);
            }
        }
        return result;    
    }

使用雙指針代替堆棧提高些許性能

    //雙指針 不使用堆棧
    public int trap3(int[] height) {
        int length = height.length;
        if(length<=2){
            return 0;
        }
        
        //獲得可以盛水的區間
        int startIndex = 0;
        while(startIndex height[startIndex]){
                for(int i = index-1 ; i > startIndex ; i--){
                    result += (height[startIndex] - height[i]);
                }
                startIndex = index;
            }else{
                for(int i = index ; i>0 && height[i] > height[i-1] ; i--){
                    result += (height[i] - height[i-1]);
                    height[i-1] = height[i];
                }
            }
        }
        return result;
    }

這里會降低代碼效率的部分主要在于，對于盛水區間的高度的計算太冗雜了。只要獲得左右木板高度的最小值，就是當前區間可以盛水的最大高度。在這里最大的問題就在于獲得最遠區間后，需要對區間內的小區間逐個遍歷。這種方法雖然一次遍歷數組就可以實現，但是還需要在子區間中反復計算才可以。

從整個數組的角度看來，如果找到區間左側的最大值leftMax，以及區間右側的最大值rightMax，就可以知道當前區間的盛水高度為Math.min(leftMax,rightMax)-height[i]。也就是傳說中的木桶理論，短板決定盛水的高度。這樣的話，代表在每個區間計算盛水值的時候，需要遍歷整個數組。遍歷整個數組，則需要O(n的平方)的時間復雜度。
這里的代碼實現并不難，可以直接參考官方提供的C++方法。

思路一中，每一次對一個區間都要遍歷整個數組才能獲得左右最大值。但是其實，從左往右遍歷一次數組，可以獲得各個區間的leftMax。同理，從右往左遍歷可以獲得各個區間的rightMax。將這兩個值都存在數組中，并對數組進行遍歷，計算各個區間的盛水高度。時間復雜度為O(n),代碼如下：

    public int trap3(int[] height){
        int length = height.length;
        //leftMax數組
        int[] left = new int[length];
        //rightMax數組
        int[] right = new int[length];
        
        int leftMax = 0;
        int rightMax = 0;
        for(int i = 0 ; i
該思路的官方講解請戳這里
這里涉及了一個解題思路，叫做Dynamic Programming。這在我之前的博客中也有所提及，但是我仍然對這個概念比較模糊。這里有一個非常好的解答帖子供大家參考。籠統的來說，就是利用已知的解答來幫助解決目標問題。看上去好像是一句廢話，但是具體實踐中有多重形式，例如遞歸，自頂向下編碼和自底向上編碼等等。這些概念還是需要通過大量的題目和代碼來感受啊。
思路三：堆棧的聰明使用
在這里，堆棧允許我們漸進的通過橫向分割而非之前傳統的縱向分割的方式來累加計算盛水量。一旦當前區間的高度超過棧頂的元素，就代表棧頂元素有一個右邊界。鑒于棧中的元素都是遞減的，所以如果存在一個比棧頂元素大的棧中元素，則一定可以確定該區間的盛水量。代碼如下：
    public int trap4(int[] height){
        int length = height.length;
        int result = 0, current = 0;
        
        Stack s = new Stack();
        
        while(current < length){
            while(!s.isEmpty() && height[current] > height[s.peek()]){
                int top = s.pop();
                if(s.isEmpty()){
                    break;
                }
                //獲得兩個節點之間的寬度
                int distance = current - s.peek() - 1;
                int tempHeight = Math.min(height[current], height[s.peek()]) - height[top];
                result += tempHeight  * distance;
            }
            s.push(current++);
        }
        return result;
    }
思路四：雙指針的進階
這里要從更高的高度來看這道題目，原文如下：

這里的意思是這樣的：
經過實踐證明，如果當前區間的leftMax換句話說，假設能找到任意一個比當前區間高度值大的值，并且假設該值位于當前區間的右側，那么該區間的盛水高度由leftMax決定。同理，如果該值位于當前區間的左側，那么該區間的盛水高度由rightMax決定。
這個結論可以使用反證法證明。
假設能找到任意一個比當前區間高度值大的值，并且假設該值位于當前區間的右側，則存在滿足這樣一個區間，該區間盛水高度由rightMax決定。
這說明，該區間的leftMax大于rightMax。假設當前區間下標為i，則一定存在一個j<=i，height[j]=leftMax。其實，縱觀雙指針的遍歷，我們可以知道，雙指針最終會停在高度最高的區間，即height[index] = Max(leftMax, rightMax)上。每一次遍歷都會將兩個指針向相對較高的位置移動。
所以一旦左指針遍歷到剛才的j節點，因為當前右指針指向的值都小于leftMax（rightMax代碼實現如下：
    public int trap5(int[] height) {
        int left = 0;
        int right = height.length - 1;
        int result = 0;
        int leftMax=0, rightMax=0;
        while(left < right){
            if(height[left] < height[right]){
                leftMax = Math.max(height[left], leftMax);
                result += leftMax - height[left];
                left++;
            }else{
                rightMax = Math.max(height[right], rightMax);
                result += rightMax - height[right];
                right--;
            }
        }
        return result;
    }

想要了解更多開發技術，面試教程以及互聯網公司內推，歡迎關注我的微信公眾號！將會不定期的發放福利哦~