[数据结构与算法]LeetCode——接雨水 C++

题目描述：

??????? 本题目乍一看雨水的数量是由多个高柱共同决定的，但是本题依然可以单独分析数组中每一个元素所对应的雨水数量，并将他们加在一起。

根据木桶效应我们可以分析出当前元素所能承装的雨水数量为其左右两边最大值（包括本身）中的较小值减去本身的大小，即：

min(left[i],right[i])-height[i]

其left与right数组中的值代表当前左右两边的最大值，用动态规划方法维护。、

完整代码如下：

????????

int trap(vector<int>& height) {
        vector<int>left(height.size(),0),right(height.size(),0);
        int num=0;
        left[0]=height[0];
        right[height.size()-1]=height[height.size()-1];
        for(int i=1;i<height.size();i++)left[i]=max(left[i-1],height[i]);
        for(int i=height.size()-2;i>=0;i--)right[i]=max(right[i+1],height[i]);
        for(int i=1;i<height.size()-1;i++)num+=min(left[i],right[i])-height[i];
        return num;
    }