算法1

思路:左右指针，一次遍历
详细解释看：https://www.acwing.com/solution/content/42818/
xia

C++ 代码

class Solution {
public:
    int trap(vector<int>& height) {
        if(height.empty())return 0;
        int n=height.size();//柱子的个数
        vector<int> left(n),right(n);//往左走的最大高度和往右走的最大高度
        left[0]=height[0],right[n-1]=height[n-1];//初始化左右边界
        //这里采用的是左右指针，一次遍历，也可以采用快慢双指针，来回遍历两次
        //每次迭代
        //1:判断h[left]与h[right]的最大值
        //2：用小的判断当前h值是否大于其方向的最大值
        //大于：说明其方向本身最大，left_max=h[left]
        //小于；说明左右都有比他大的可以盛水，ans=(left_max-h[left])
        //3:小的向前走，直到左右指针相遇
        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]);
            int res=0;
        for(int i=0;i<n;i++)
            res+=min(left[i],right[i])-height[i];
        return res;

    }
};