leetcode-42. 接雨水

class Solution {
public:
    int trap(vector<int>& height) {

        vector<int> left(height.size(),0);
        vector<int> right(height.size(),0);
        int lefttemp = 0;
        int righttemp = 0;
        // 最左边的接不了雨水
        for(int i = 1; i < height.size(); i++){ 
            lefttemp = max(lefttemp, height[i-1]);
            left[i] = lefttemp;  // left[i] 记录当前i左边的最大值
        }

        // 最右边的接不了雨水
        for(int i = height.size()-2; i >=0; i--){
            righttemp = max(righttemp, height[i+1]);
            right[i] = righttemp;  // right[i] 记录当前i右边的最大值
        }
        
        int res = 0;
        // 注意两头的不用判断，肯定接不了雨水
        for(int i = 1; i < height.size()-1;i++){
            int minval = min(left[i],right[i]);
            if(minval>height[i])
                res = res + (minval - height[i]);
        }
        return res;
    }
};