给定n个表示高度的非负整数，其中每个条的宽度为1，计算下雨后它能捕获多少水。
Input：[0,1,0,2,1,0,1,3,2,1,2,1]
Output：6
Method 1
以数组中最大值为标准，area=max×len(height)。每次循环都减掉没有达到最大值的部分的那层。如下图，第一次减掉黄色的部分，第二次减掉蓝色的部分，第三次减掉粉色的部分。最后结果减掉所有数的和，剩下的就是装水量。
用l和r代表左右两侧，每次l从0开始，r从数组的长度开始向中间合并。当l或者r位置的值小于数组的最大值时用area减当前位置的数。
class Solution:def trap(self, height: List[int]) -> int:len_val=len(height)if not height or len_val < 3:return 0 max_val=max(height)res=max_val*len(height)for i in range(1,max_val+1):l = 0r = len_val - 1while height[l]<i:res-=1l+=1while height[r]<i:res-=1r-=1return res-sum(height)
Method 2
与第一个方法相反，将area相加。与11题最大装水量相似。
1. 定义l，r为左右指针，l_max和r_max存储左右指针遍历过的数字的最大值，res用来存储每次蓄水量。
l, r, l_max, r_max, res=0, len(height), 0, 0, 0
2. 当l小于r时，寻找l_max的最大值，将l_max最大值与height[l]做差，加到res中，l向前挪一位；l大于等于r时同理。这样就保证每次都会有一个值能困住水。
class Solution:def trap(self, height):n = len(height)if not height or n < 3:return 0l, r = 0, n-1l_max, r_max = 0, 0res = 0 while l < r:if height[l] < height[r]:l_max = max(l_max, height[l])res += l_max - height[l]l += 1else:r_max = max(r_max, height[r])res += r_max - height[r]r -= 1return res