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

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

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

題目如下：

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

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

示例

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

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

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

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

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

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

  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

解法二 雙指針法

前面說過，這種方法又稱為改進(jìn)的動(dòng)態(tài)規(guī)劃法，是因?yàn)樗褪窃诮夥ㄒ坏幕A(chǔ)上衍生出來的。由于解法一中，數(shù)組中存儲(chǔ)的每個(gè)數(shù)值只用過一次就不再使用，那能不能在用的時(shí)候算一次就好呢？

用兩個(gè)指針從左右同時(shí)出發(fā)，這樣可以分別獲得左側(cè)和右側(cè)的最高柱子高度。由于存雨量取決左右最高柱子高度的較小者，因此，對(duì)于左指針?biāo)傅奈恢脕碚f，一旦其左側(cè)最大值比右側(cè)的已知的最高高度小，則可以判定其左側(cè)最大值比右側(cè)的真實(shí)的最高高度（目前未知）小。這時(shí)左指針?biāo)肝恢玫挠炅靠梢杂?jì)算（如圖藍(lán)色部分），右側(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)棧法

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

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

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

ill.png

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

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

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

def trap(self, height: List[int]) -> int:
        if not height:
            return 0
        stack = []  # 存儲(chǔ)高度的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

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