1. 原始题目
给定 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
2. 思路
最简单的想法：对于每个元素都要考虑它能接多少雨水：
第一个元素是0，能接0雨水
第二个元素是1，能接0雨水
第三个元素是0，能接1雨水
...
第六个元素是0，能接2雨水。
可以看到，每个元素能接的雨水量是：当前位置左边最高的数与右边最高的数的最小值减去当前位置的数。
例如第六个元素接水量为2 = min(2,3)-0=2。
按照这个思路可以写一个最简单的代码:
3. 解题
1 class Solution:
2 def trap(self, height):
3 if not height: return 0
4 n = len(height)
5 left,right = [0]*n, [0]*n # 每个位置都存放其左边最大值和右边最大值
6 temp = 0
7 for i in range(n):
8 temp= max(temp,height[i]) # 找每个元素的左边最大值（含自身）
9 left[i] = temp
10 temp = 0
11 for i in range(n-1,-1,-1):
12 temp = max(temp,height[i]) # 找每个元素的右边最大值（含自身）
13 right[i] = temp
14 res = 0
15 for i in range(n):
16 res+=min(left[i],right[i])-height[i] # 最小的高度值-自身
17 return res