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

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.

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

這里先講一講我在拿到這個(gè)題目時(shí)候的思路。我先通過堆棧的方法，找到一個(gè)封閉區(qū)間，該區(qū)間可以盛水，該區(qū)間的右節(jié)點(diǎn)可以作為下一個(gè)封閉區(qū)間的起點(diǎn)。這種方法思路非常直接，但是并不是高效的計(jì)算機(jī)思維。
堆棧的方法如下：

    //使用堆棧，分別存儲(chǔ)值和下標(biāo)
    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{
                //如果當(dāng)前值比最左值小，則說明該盛水區(qū)間仍然沒到最右點(diǎn)
                int count = 1;
                //將所有比當(dāng)前值小的區(qū)間填滿，并將水平區(qū)間的個(gè)數(shù)插入棧中
                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;
        }
        
        //獲得可以盛水的區(qū)間
        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;
    }

這里會(huì)降低代碼效率的部分主要在于，對(duì)于盛水區(qū)間的高度的計(jì)算太冗雜了。只要獲得左右木板高度的最小值，就是當(dāng)前區(qū)間可以盛水的最大高度。在這里最大的問題就在于獲得最遠(yuǎn)區(qū)間后，需要對(duì)區(qū)間內(nèi)的小區(qū)間逐個(gè)遍歷。這種方法雖然一次遍歷數(shù)組就可以實(shí)現(xiàn)，但是還需要在子區(qū)間中反復(fù)計(jì)算才可以。

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

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

    public int trap3(int[] height){
        int length = height.length;
        //leftMax數(shù)組
        int[] left = new int[length];
        //rightMax數(shù)組
        int[] right = new int[length];
        
        int leftMax = 0;
        int rightMax = 0;
        for(int i = 0 ; i
該思路的官方講解請(qǐng)戳這里
這里涉及了一個(gè)解題思路，叫做Dynamic Programming。這在我之前的博客中也有所提及，但是我仍然對(duì)這個(gè)概念比較模糊。這里有一個(gè)非常好的解答帖子供大家參考?；\統(tǒng)的來說，就是利用已知的解答來幫助解決目標(biāo)問題?？瓷先ズ孟袷且痪鋸U話，但是具體實(shí)踐中有多重形式，例如遞歸，自頂向下編碼和自底向上編碼等等。這些概念還是需要通過大量的題目和代碼來感受啊。
思路三：堆棧的聰明使用
在這里，堆棧允許我們漸進(jìn)的通過橫向分割而非之前傳統(tǒng)的縱向分割的方式來累加計(jì)算盛水量。一旦當(dāng)前區(qū)間的高度超過棧頂?shù)脑?，就代表?xiàng)ｍ斣赜幸粋€(gè)右邊界。鑒于棧中的元素都是遞減的，所以如果存在一個(gè)比棧頂元素大的棧中元素，則一定可以確定該區(qū)間的盛水量。代碼如下：
    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;
                }
                //獲得兩個(gè)節(jié)點(diǎn)之間的寬度
                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;
    }
思路四：雙指針的進(jìn)階
這里要從更高的高度來看這道題目，原文如下：

這里的意思是這樣的：
經(jīng)過實(shí)踐證明，如果當(dāng)前區(qū)間的leftMax換句話說，假設(shè)能找到任意一個(gè)比當(dāng)前區(qū)間高度值大的值，并且假設(shè)該值位于當(dāng)前區(qū)間的右側(cè)，那么該區(qū)間的盛水高度由leftMax決定。同理，如果該值位于當(dāng)前區(qū)間的左側(cè)，那么該區(qū)間的盛水高度由rightMax決定。
這個(gè)結(jié)論可以使用反證法證明。
假設(shè)能找到任意一個(gè)比當(dāng)前區(qū)間高度值大的值，并且假設(shè)該值位于當(dāng)前區(qū)間的右側(cè)，則存在滿足這樣一個(gè)區(qū)間，該區(qū)間盛水高度由rightMax決定。
這說明，該區(qū)間的leftMax大于rightMax。假設(shè)當(dāng)前區(qū)間下標(biāo)為i，則一定存在一個(gè)j<=i，height[j]=leftMax。其實(shí)，縱觀雙指針的遍歷，我們可以知道，雙指針最終會(huì)停在高度最高的區(qū)間，即height[index] = Max(leftMax, rightMax)上。每一次遍歷都會(huì)將兩個(gè)指針向相對(duì)較高的位置移動(dòng)。
所以一旦左指針遍歷到剛才的j節(jié)點(diǎn)，因?yàn)楫?dāng)前右指針指向的值都小于leftMax（rightMax代碼實(shí)現(xiàn)如下：
    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;
    }

想要了解更多開發(fā)技術(shù)，面試教程以及互聯(lián)網(wǎng)公司內(nèi)推，歡迎關(guān)注我的微信公眾號(hào)！將會(huì)不定期的發(fā)放福利哦~