42. Trapping Rain Water
这题的思路比较简单明确，就是找出当前点的左边最高和右边最高，然后取其中的小值来减去当前的高度就是当前点的蓄水量了。
class Solution(object):
def trap(self, height):
"""
:type height: List[int]
:rtype: int
"""
# 这道题的思路就是找到一个值左边的最高点和右边的最高点，然后取短的并且减去当前的值
if not height or len(height) <= 2:
return 0
left = [0]
for i in range(1, len(height)):
left.append(max(height[i-1], left[-1]))
right = [0]
for i in range(len(height)-2, -1, -1):
right = [max(right[0], height[i+1])] + right
res = 0
for i in range(1, len(height)-1):
res += max(min(left[i], right[i]) - height[i], 0)
return res
