题目链接
难度：困难 类型： 栈
给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。
示例
输入: [0,1,0,2,1,0,1,3,2,1,2,1]
输出: 6
解题思路
图片来源于 https://leetcode-cn.com/problems/two-sum/solution/jie-yu-shui-by-leetcode/
- 找到数组中从下标 i 到最左端最高的条形块高度
。
- 找到数组中从下标 i 到最右端最高的条形块高度
。
- 扫描数组
并更新答案：
累加到 总面积上
代码实现
class Solution(object):
def trap(self, height):
"""
:type height: List[int]
:rtype: int
"""
max_left = [0]
for h in height:
max_left.append(max(max_left[-1], h))
max_right = 0
res = 0
n = len(height)
for i in range(n):
max_right = max(max_right, height[n-i-1])
res += min(max_right, max_left[n-i]) - height[n-i-1]
return res
