4.4日：接雨水
给定n个非负整数表示每个宽度为1的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。
- 找出最高点
- 分别从两边往最高点遍历：如果下一个数比当前数小，说明可以接到水
class Solution(object):def trap(self, height):""":type height: List[int]:rtype: int"""if len(height) <= 1:return 0max_height = 0max_height_index = 0# 找到最高点for i in range(len(height)):h = height[i]if h > max_height:max_height = hmax_height_index = iarea = 0# 从左边往最高点遍历tmp = height[0]for i in range(max_height_index):if height[i] > tmp:tmp = height[i]else:area = area + (tmp - height[i])# 从右边往最高点遍历tmp = height[-1]for i in reversed(range(max_height_index + 1, len(height))):if height[i] > tmp:tmp = height[i]else:area = area + (tmp - height[i])return area