题目

双指针

思路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