1 题目
给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。
2 解析
（1）方法一：栈
将墙的高度入栈，当新元素小于栈顶元素，就入栈，反之就出栈，并计算凹槽内的长和宽。最后将每个长方形面积求和。
注意：凹槽的高度是由 min(凹槽左边高度, 凹槽右边高度) - 凹槽底部高度 来计算的。如下图的是左边的2号柱子的高度建议1号柱子的高度。
凹槽的宽度是由凹槽右边的下标 – 凹槽左边的下标 – 1（因为只求中间宽度）来计算的。
3 Python实现
class Solution: def trap(sel, height: List[int]) -> int: stack = [] result = 0 for i in range(len(height)): if not stack: stack.append(i) elif height[i]<height[stack[-1]]: stack.append(i) else: while stack and height[stack[-1]]<height[i]: # index = stack[-1] stack.pop() if stack: h = min(height[i],height[stack[-1]])-height[index] w = i - stack[-1]-1 result +=w*h stack.append(i) return result
