给定一个直方图(也称柱状图)，假设有人从上面源源不断地倒水，最后直方图能存多少水量?直方图的宽度为 1。

上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的直方图，在这种情况下，可以接 6 个单位的水（蓝色部分表示水）。 感谢 Marcos 贡献此图。

示例:

输入: [0,1,0,2,1,0,1,3,2,1,2,1]
输出: 6

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/volume-of-histogram-lcci
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

题解： 可以看出每个蓄水处的水量等于从此位置
m i n ( 向 左 的 最 高 的 高 度 , 向 右 最 高 的 高 度 ) − 自 身 的 高 度 min(向左的最高的高度,向右最高的高度)-自身的高度 min(向左的最高的高度,向右最高的高度)−自身的高度
先算出每个点向左的最高高度，每个点向右的最高高度
然后根据式子计算累加

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