我的原文鏈接：http://ben-personal.top/2020/04/leetcode-42-traprain/
這道題將對(duì)比三種方法鲁僚，分別是動(dòng)態(tài)規(guī)劃族阅、雙指針（改進(jìn)的動(dòng)態(tài)規(guī)劃）和單調(diào)棧法槽卫。通過(guò)這道題至少可以感受到兩方面的進(jìn)步：
- 看問(wèn)題的視角不同菠净，形成的算法也完全不同
- 動(dòng)態(tài)規(guī)劃常掣矢模可以進(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] #反過(guò)來(lái)的
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
解法二 雙指針?lè)?/h2>
前面說(shuō)過(guò)，這種方法又稱為改進(jìn)的動(dòng)態(tài)規(guī)劃法叼旋，是因?yàn)樗褪窃诮夥ㄒ坏幕A(chǔ)上衍生出來(lái)的仇哆。由于解法一中，數(shù)組中存儲(chǔ)的每個(gè)數(shù)值只用過(guò)一次就不再使用夫植，那能不能在用的時(shí)候算一次就好呢讹剔？
用兩個(gè)指針從左右同時(shí)出發(fā)油讯，這樣可以分別獲得左側(cè)和右側(cè)的最高柱子高度。由于存雨量取決左右最高柱子高度的較小者延欠，因此陌兑，對(duì)于左指針?biāo)傅奈恢脕?lái)說(shuō)，一旦其左側(cè)最大值比右側(cè)的已知的最高高度小由捎，則可以判定其左側(cè)最大值比右側(cè)的真實(shí)的最高高度（目前未知）小兔综。這時(shí)左指針?biāo)肝恢玫挠炅靠梢杂?jì)算（如圖藍(lán)色部分），右側(cè)同理狞玛。
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ì)難以理解一些，不過(guò)提供了另一個(gè)看問(wèn)題的角度心肪。前兩種方法是逐列統(tǒng)計(jì)雨量的锭亏，而單調(diào)棧法則是分塊逐層統(tǒng)計(jì)雨量。
所謂單調(diào)棧硬鞍，是指棧中元素是絕對(duì)有序的慧瘤。當(dāng)即將入棧的值不符合棧中的順序時(shí)，則需要將棧頂元素出棧固该，直到能夠滿足順序時(shí)才能入棧锅减。
就本題而言，考慮一個(gè)單調(diào)遞減的棧伐坏，即棧頂元素最小上煤。因?yàn)楫?dāng)后入棧的柱子高度較小時(shí)，是不可能存下雨水的（見(jiàn)下圖）著淆。只有當(dāng)即將入棧的柱子高度比棧頂?shù)拇髸r(shí)劫狠，才開(kāi)始存下雨水。
那具體存下了多少呢永部？從棧頂即將出棧的柱子來(lái)看（圖中右側(cè)第二個(gè)）独泞，雨量加上本身的高度不能超過(guò)左右柱子中較低者，故雨量為深藍(lán)部分苔埋。
當(dāng)此柱子出棧后懦砂，繼續(xù)比較棧頂元素與即將入棧的柱子高度，發(fā)現(xiàn)仍然小组橄，那仍然可以存下雨水荞膘，其雨量為（左右柱子中較低者-本身的高度）*2，即淺藍(lán)部分玉工。為什么乘2羽资？從圖中容易看出，上一個(gè)出棧的元素并沒(méi)有考慮到這一部分雨量遵班。
直到棧頂柱子比即將入棧的柱子高或棧為空時(shí)屠升，將此柱子入棧潮改。總的來(lái)說(shuō)腹暖，從圖像可以看出汇在，這是分層計(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
通過(guò)對(duì)動(dòng)態(tài)規(guī)劃的改進(jìn)糕殉，我們發(fā)現(xiàn)，當(dāng)動(dòng)態(tài)規(guī)劃的數(shù)組中元素利用率低時(shí)殖告，常巢诼螅可以改進(jìn)算法，節(jié)省空間丛肮。同時(shí)，通過(guò)本問(wèn)題魄缚，也可以了解單調(diào)棧的應(yīng)用宝与，類似的數(shù)據(jù)結(jié)構(gòu)還有單調(diào)隊(duì)列，可以自行學(xué)習(xí)冶匹。
