https://leetcode.cn/problems/trapping-rain-water/?envType=study-plan-v2&envId=top-100-liked
####题目关键在于：找出最大前缀与最大后缀，min(左边max,右边max)，所盛水的容量=min-h

开两个数组，分别存储每个柱子左侧右侧的最大值，左侧最大值从1开始算，每次=前一个柱子处的最大值与当前柱子的高度相比较，因此要注意循环下标和初始化问题，l[0]=height[0];r[n-1]=height[n-1];计算右侧最大值时应当从n-2下标开始算起

class Solution {
public:
    int trap(vector<int> &height) {
       int n=height.size();
       int l[n];
       int r[n];
       l[0]=height[0];
       for(int i=1;i<n;i++)
        l[i]=max(l[i-1],height[i]);
       r[n-1]=height[n-1];
       for(int i=n-2;i>=0;i--)
        r[i]=max(r[i+1],height[i]);
        int res=0;
        for(int i=0;i<n;i++)
         res+=min(l[i],r[i])-height[i];
        return  res;
    }
};

优化版本，就是利用两个指针，不额外开两个数组，判断左右两边哪个小就选择哪个

不是很理解。。。。。。

class Solution:
    def trap(self, height: List[int]) -> int:
        ans = left = pre_max = suf_max = 0
        right = len(height) - 1
        while left < right:
            pre_max = max(pre_max, height[left])
            suf_max = max(suf_max, height[right])
            if pre_max < suf_max:
                ans += pre_max - height[left]
                left += 1
            else:
                ans += suf_max - height[right]
                right -= 1
        return ans