https://leetcode-cn.com/problems/trapping-rain-water/
给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。
输入: [0,1,0,2,1,0,1,3,2,1,2,1] 输出: 6单调栈思路：https://zhuanlan.zhihu.com/p/125074613
维持栈内的柱子height值是单调递减的，若出现个更高的柱子，则不断pop出小于当前高柱子的所有元素。（注意：栈存的是index，index是一直增的，单调栈的单调递减指的是值height递减）
简单来说就是当前柱子如果小于等于栈顶元素，说明形不成凹槽，则将当前柱子入栈；反之若当前柱子大于栈顶元素，说明形成了凹槽，于是将栈中小于当前柱子的元素pop出来，将凹槽的大小累加到结果中。
top = monotonicStack.pop() bottomHeight = height[top] # 栈中最低点的高度 leftUpperIndex = monotonicStack[-1] # 左轴index heightDiff = min(height[leftUpperIndex], v) - bottomHeight # 高度差 width = i - leftUpperIndex - 1 # 宽度差栈存的是index
如图，栈中元素index从[3, 4, 6] 到 [7] 的过程 （print(stack)结果见下面的代码片）
while pop出 索引6
top = 6， bottomHeight = 1leftUpperIndex = 4heightDiff = min（1， 3） - 1 = 0，即min（index4值，index7值）- index6值 ， width = 7 - 4 - 1 = 2heightDiff * width = 0while继续pop出 索引4
top = 4， bottomHeight = 1leftUpperIndex = 3heightDiff = min（2， 3） - 1 = 1 ，即min（index3值，index7值）- index4值 ， width = 7 - 3 - 1 = 3heightDiff * width = 1 * 3 = 3 [0] [1] [1, 2] [3] [3, 4] [3, 4, 5] [3, 4, 6] [7] [7, 8] [7, 8, 9] [7, 8, 10] [7, 8, 10, 11] class Solution(object): def trap(self, height): """ :type height: List[int] :rtype: int """ monotonicStack = [] # 单调栈：栈维护value从底到顶递增，但是存的是索引i！ res = 0 for i, v in enumerate(height): while len(monotonicStack) > 0 and height[monotonicStack[-1]] < v: # 连续pop出“比v小的数” top = monotonicStack.pop() bottomHeight = height[top] # 栈中最低点的高度 if len(monotonicStack) == 0: break leftUpperIndex = monotonicStack[-1] # 左轴index heightDiff = min(height[leftUpperIndex], v) - bottomHeight # 高度差 width = i - leftUpperIndex - 1 # 宽度差 res += heightDiff * width monotonicStack.append(i) # 压栈：index # print(monotonicStack) return res height = [0,1,0,2,1,0,1,3,2,1,2,1] s = Solution() print(s.trap(height))视频 https://leetcode-cn.com/problems/trapping-rain-water/solution/xiong-mao-shua-ti-python3-shi-pin-jiang-jie-dan-di/
待续
