给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。
示例 1：
输入：height = [0,1,0,2,1,0,1,3,2,1,2,1]
输出：6
解释：上面是由数组
[0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图，在这种情况下，可以接 6 个单位的雨水（蓝色部分表示雨水）。
示例 2：
输入：height = [4,2,0,3,2,5]
输出：9
提示：
n == height.length 1 <= n <= 2 * 104 0 <= height[i] <= 105
我最开始的思路是将这道题转化为一道数学问题：能影响每个单位的储水量的是左右两边柱子的最大值（即最高的柱子），而决定储水量的则是这两个值中最小的值。所以我们只需要创建两个数组，分别储存每个单位的左边和右边的最大值，然后再次遍历，进行比较，如果该单位柱子均低于左右两边最大值（也就是呈现“凹”字型），那就是可储水，再计算两边最低的柱子高度当作储水量即可。
思路没问题，通过了很多测试用例，但在height数组数量较大时，却出现了超时的问题。
继续改进。
1.时间超出限制主要是因为我使用了很多max和min，那么可以使用递归来降低时间复杂度，创建left_max和right_max数组，每次比较的是当前height中的数值和前一个位置的left_max，从而取出最大的当前位置的left_max，而不是每次都要算一遍前面所有高度的max。
2.添加了n==0就return0的条件，更严谨了。
# 31ms 14.2mb
class Solution(object):def trap(self, height):""":type height: List[int]:rtype: int"""n = len(height)if n == 0:return 0left_max = [0]*nright_max = [0]*nleft_max[0] = height[0]for i in range(1,n):left_max[i] = max(height[i], left_max[i-1])right_max[n-1] = height[n-1]for i in range(n-2,-1,-1):right_max[i] = max(height[i], right_max[i+1])ans = 0for i in range(n):ans += min(left_max[i], right_max[i]) - height[i]return ans
