我的原文鏈接：http://ben-personal.top/2020/04/leetcode-42-traprain/

這道題將對比三種方法，分別是動態(tài)規(guī)劃、雙指針（改進的動態(tài)規(guī)劃）和單調(diào)棧法。通過這道題至少可以感受到兩方面的進步：

• 看問題的視角不同，形成的算法也完全不同
• 動態(tài)規(guī)劃常?？梢赃M行空間上的改進

題目如下：

給定 n 個非負整數(shù)表示每個寬度為 1 的柱子的高度圖，計算按此排列的柱子，下雨之后能接多少雨水。

數(shù)組 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度圖如下，在這種情況下，可以接 6 個單位的雨水（藍色部分表示雨水）。

示例

解法一 動態(tài)規(guī)劃

這一方法的基本思想在于，任一位置的存雨量取決于其左右最高柱子的較小者，這也是所謂木桶效應，最終值應為：

min{左邊最高柱子高度，右邊最高柱子高度} - 該位置柱子高度

那這和動態(tài)規(guī)劃有何關(guān)系呢？關(guān)鍵就在于左右最高柱子的高度獲取上。如果迭代到每個位置都重新計算一遍左右最高柱子，顯然是不合算的。如果能發(fā)現(xiàn)相鄰位置之間的如下關(guān)系：

# 記H(i)為柱子i左邊最高的柱子高度，則
H(i+1)=max{柱子i的高度，H(i)}

那就意味著不必每次重新計算，如果存儲下這些數(shù)據(jù)，則可節(jié)省大量的時間。
由此誕生動態(tài)規(guī)劃法，用兩個數(shù)組存下每個位置左右的最大高度即可：

  def trap(self, height: List[int]) -> int:
        num_cols = len(height)
        if num_cols < 3:
            return 0
        ans = 0
        h_left = [0]
        h_right = [0] #反過來的
        for i in range(num_cols-1):
            h_left.append(max(height[i], h_left[-1]))
            h_right.append(max(height[num_cols-1-i], h_right[-1]))

        for i in range(num_cols):
            ans += max(0, min(h_left[i], h_right[num_cols-1-i]) - height[i])
        return ans

解法二 雙指針法

前面說過，這種方法又稱為改進的動態(tài)規(guī)劃法，是因為它就是在解法一的基礎(chǔ)上衍生出來的。由于解法一中，數(shù)組中存儲的每個數(shù)值只用過一次就不再使用，那能不能在用的時候算一次就好呢？

用兩個指針從左右同時出發(fā)，這樣可以分別獲得左側(cè)和右側(cè)的最高柱子高度。由于存雨量取決左右最高柱子高度的較小者，因此，對于左指針所指的位置來說，一旦其左側(cè)最大值比右側(cè)的已知的最高高度小，則可以判定其左側(cè)最大值比右側(cè)的真實的最高高度（目前未知）小。這時左指針所指位置的雨量可以計算（如圖藍色部分），右側(cè)同理。

ill.png

    def trap(self, height: List[int]) -> int:
        ans = 0
        left = 0 # 左指針的index
        h_left = 0  # 左側(cè)最高的高度
        right = len(height) - 1 # 右指針的index
        h_right = 0  # 右側(cè)最高的高度
        while left <= right:
            if h_left > h_right:  # 意味著h_left也 >right，也 >h_right
                h_right = max(height[right], h_right)
                ans += h_right - height[right]
                right -= 1
            else:
                h_left = max(height[left], h_left)
                ans += h_left - height[left]
                left += 1
        return ans

解法三 單調(diào)棧法

這種方法相對難以理解一些，不過提供了另一個看問題的角度。前兩種方法是逐列統(tǒng)計雨量的，而單調(diào)棧法則是分塊逐層統(tǒng)計雨量。

所謂單調(diào)棧，是指棧中元素是絕對有序的。當即將入棧的值不符合棧中的順序時，則需要將棧頂元素出棧，直到能夠滿足順序時才能入棧。

就本題而言，考慮一個單調(diào)遞減的棧，即棧頂元素最小。因為當后入棧的柱子高度較小時，是不可能存下雨水的（見下圖）。只有當即將入棧的柱子高度比棧頂?shù)拇髸r，才開始存下雨水。

ill.png

那具體存下了多少呢？從棧頂即將出棧的柱子來看（圖中右側(cè)第二個），雨量加上本身的高度不能超過左右柱子中較低者，故雨量為深藍部分。

當此柱子出棧后，繼續(xù)比較棧頂元素與即將入棧的柱子高度，發(fā)現(xiàn)仍然小，那仍然可以存下雨水，其雨量為（左右柱子中較低者-本身的高度）*2，即淺藍部分。為什么乘2？從圖中容易看出，上一個出棧的元素并沒有考慮到這一部分雨量。

直到棧頂柱子比即將入棧的柱子高或棧為空時，將此柱子入棧。總的來說，從圖像可以看出，這是分層計算雨量，與之前的解法角度明顯不同。實現(xiàn)代碼如下：

def trap(self, height: List[int]) -> int:
        if not height:
            return 0
        stack = []  # 存儲高度的index
        ans = 0 # 結(jié)果雨水量
        for i in range(len(height)):
            if stack:
                if height[i] <= height[stack[-1]]:
                    stack.append(i)
                else:
                    while height[i] > height[stack[-1]]:
                        stackTop = stack.pop()
                        while stack and height[stack[-1]] == height[stackTop]:
                            stackTop = stack.pop()
                        if stack:
                            ans += (i-stack[-1]-1) * (min(height[i], height[stack[-1]])-height[stackTop])
                        else:
                            break
                    stack.append(i)
                    
            else:
                if height[i] != 0:
                    stack.append(i)
        return ans

通過對動態(tài)規(guī)劃的改進，我們發(fā)現(xiàn)，當動態(tài)規(guī)劃的數(shù)組中元素利用率低時，常?？梢愿倪M算法，節(jié)省空間。同時，通過本問題，也可以了解單調(diào)棧的應用，類似的數(shù)據(jù)結(jié)構(gòu)還有單調(diào)隊列，可以自行學習。