## 单调栈 1. 为什么选择单调栈，以及单调栈中的单调性为什么如此设计 2. 单调栈中放入什么元素，单调性靠什么维持 3. 是如何利用单调栈中的信息构造出凹槽的 ```python class Solution: def trap(self, height: List[int]) -> int: # 单调栈 # 借助单调栈中的信息来构造可能出现的凹槽 # 保证'栈底到栈顶'是单调递减的, 记下一个检查入栈的元素为v # 若v == height[ st[ -1 ] ] 和栈顶的前一个元素,无法形成凹槽 # 若v < height[ st[ -1 ] ] 和栈顶的前一个元素无法形成凹槽 # 若v > height[ st[ -1 ] ] 是否和栈顶的前一个元素可以形成凹槽 -> 每一个栈顶元素出栈 计算组成的凹槽大小 n = len( height ) st = [] ans = 0 for i, v in enumerate( height ): # 保证栈内元素均小于栈顶元素 while st and v > height[ st[ -1 ] ]: right = v middle = height[ st.pop() ] if st: left = height[ st[ -1 ] ] # 计算长宽 h = min( left, right ) - middle w = i - st[ -1 ] - 1 ans += ( h * w ) st.append( i ) return ans ``` ## 左右最大求雨水面积 1. 这是一种很直接的想法 2. ```python class Solution: # 给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。 # Case1: [0,1,0,2,1,0,1,3,2,1,2,1] # Case2: [4,2,0,3,2,5] def trap(self, height: List[int]) -> int: # 对于'柱子i'能够接取多少雨水 取决于'柱子i'左右最大柱子的高度 # 求'柱子i'左边第一个更大柱子 和 ‘柱子i’右边第一个更大柱子 # 进而确定'柱子i'左右最大的柱子高度，两者形成的凹陷就是'柱子i'能够接纳的雨水容积 n = len( height ) left_max = [ 0 for _ in range( n ) ] right_max = [ 0 for _ in range( n ) ] # 求右边最大 for i in range( n - 2, -1, -1 ): right_max[ i ] = max( right_max[ i + 1 ], height[ i + 1 ] ) # 求左边最大 for i in range( 1, n - 1 ): left_max[ i ] = max( left_max[ i - 1 ], height[ i - 1 ] ) # 求雨水面积 ans = 0 for i, v in enumerate( height ): if left_max[ i ] > v and right_max[ i ] > v: # 形成凹陷 ans += ( min( left_max[ i ], right_max[ i ] ) - v ) return ans ```