42. 接雨水¶
https://leetcode-cn.com/problems/trapping-rain-water/
给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。
上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图，在这种情况下，可以接 6 个单位的雨水（蓝色部分表示雨水）。 感谢 Marcos 贡献此图。
示例:
输入: [0,1,0,2,1,0,1,3,2,1,2,1]
输出: 6
FYI:
首先理解``单调栈 Monotone Stack``，以``单调递减栈``为例，比如有一家店在发 free food，很多人在排队，于是你也赶过去凑热闹。但是由于来晚了，队伍已经很长了，想着不然就插个队啥的。但发现排在队伍最前面的都是一些有纹身的大佬，惹不起。于是往队伍后面走，发现是一群小屁孩，直接全部撵走，然后排在了社会大佬们的后面。那么这就是一个单调递减的栈，按实力递减。
单调栈的一大优势就是线性的时间复杂度，所有的元素只会进栈一次，而且一旦出栈后就不会再进来了
单调递减栈可以找到
左起第一个比当前数字大的元素单调递增栈可以找到
左起第一个比当前数字小的元素
对于此题，如果能盛水，需要两边高，中间低。
使用一个单调递减栈，将递减的边界存进去，一旦发现当前的数字大于栈顶元素了，那么就有可能会有能装水的地方产生。此时我们当前的数字是右边界，我们从栈中至少需要有两个数字，才能形成一个坑槽，先取出的那个最小的数字，就是坑槽的最低点，再次取出的数字就是左边界，我们比较左右边界，取其中较小的值为装水的边界，然后此高度减去水槽最低点的高度，乘以左右边界间的距离就是装水量。
注意：栈中存的数字并不是递减的高度，而是递减的高度的坐标
备注
时间复杂度：O(n)
单次遍历 O(n) ，每个条形块最多访问两次（由于栈的弹入和弹出），并且弹入和弹出栈都是 O(1) 的
空间复杂度：O(n)
栈最多在阶梯型或平坦型条形块结构中占用 O(n) 的空间
class Solution(object):
def trap(self, height):
"""
:type height: List[int]
:rtype: int
"""
if not height or len(height) < 3:
return 0
res = 0
stack = []
for i in range(len(height)):
# 每次循环，其实是在填平
while stack and height[stack[-1]] < height[i]:
bottom_index = stack.pop()
if not stack:
break
res += (min(height[stack[-1]], height[i]) - height[bottom_index]) * (i - stack[-1] - 1)
stack.append(i)
return res