題目

雙指針

思路1

使用參數存儲從左往右（從右往左同理）遍歷時的最高的柱子，
然后移動左右的指針，每次移動左右指針中偏向小的，
如果當前指針指的柱子小于最高的柱子，就會存在接到水。

思路2

把水看作柱子，那么整個柱子都會變成凸的樣子，不會出現凹的情況（如果有凹，會被水填滿）
那么我們的參數l_max，r_max就是在記錄凸的地方，和height里的凹的數據進行比較，記錄雨水。

class Solution(object):def trap(self, height):  len_h = len(height)l, r = 0, len_h - 1l_max, r_max = 0, 0ans = 0while l < r:l_max = max(l_max, height[l])r_max = max(r_max, height[r])if height[l] < height[r]:ans += l_max - height[l]l += 1else:ans += r_max - height[r]r -= 1return ans

動態規劃

思路：分別記錄從左到右/從右到左的的最高柱子，思路和雙指針一樣

class Solution:def trap(self, height: List[int]) -> int:if not height:return 0n = len(height)leftMax = [height[0]] + [0] * (n - 1)for i in range(1, n):leftMax[i] = max(leftMax[i - 1], height[i])rightMax = [0] * (n - 1) + [height[n - 1]]for i in range(n - 2, -1, -1):rightMax[i] = max(rightMax[i + 1], height[i])ans = sum(min(leftMax[i], rightMax[i]) - height[i] for i in range(n))return ans

前后綴分解

思路：和雙指針思路相似，記錄兩邊的最高柱

class Solution(object):def trap(self, height):""":type height: List[int]:rtype: int"""n = len(height)# pre_max = [0] * n# pre_max[0] = height[0]pre_max = height.copy()for i in range(1, n):pre_max[i] = max(pre_max[i-1], height[i])suf_max = [0] * n  # suf_max[i] 表示從 height[i] 到 height[n-1] 的最大值suf_max[-1] = height[-1]for i in range(n - 2, -1, -1):suf_max[i] = max(suf_max[i + 1], height[i])ans = 0for h, pre, suf in zip(height, pre_max, suf_max):ans += min(pre, suf) - h #累計每個水桶能接多少水return ans 

棧

思路：

1. 使用棧按單調遞減記錄左邊柱子的情況
2. 當識別到高于目前棧頂的元素的時候，不斷彈出棧頂的元素（作為坑底），將棧前一個元素作為左邊界，當前元素h作為右邊界，橫著計算水坑。while循環就是不斷地計算橫著的水坑，直到識別到左邊沒有合適的邊界無法形成水坑/左邊的邊界大于當前元素。
3. 最后將目前的柱子推入棧。

注意 while 中加了等號，這可以讓棧中沒有重復元素，從而在有很多重復元素的情況下，使用更少的空間。

class Solution(object):def trap(self, height):""":type height: List[int]:rtype: int"""ans = 0st = []for i, h in enumerate(height):# 當棧不為空，且當前高度大于棧頂索引對應的高度時while st and height[st[-1]] <= h: bottom_h = height[st.pop()] # 彈出棧頂元素，這個位置將作為"水坑底部"if not st: # 如果棧空了，說明左邊沒有更高的邊界，無法形成水坑break  left = st[-1] # 此時棧頂元素就是左邊界dh = min(height[left], h) - bottom_h # 計算水坑的高度：左右邊界中較低的那個減去底部高度ans += dh * (i - left - 1)# 計算水坑的寬度：當前位置到左邊界的距離減1st.append(i) # 把當前位置加入棧，保持棧的單調遞減特性return ans