8ms cpp solution using two vector


  • 0
    Y
    int trap(vector<int>& height) {
        int n=height.size(), left_num=INT_MIN, right_num=INT_MIN;
        int sum_height=0, sum_water=0;
        vector<int> left(n), right(n);
        for (int i=0; i<n; i++){
            left_num = (height[i]>left_num)? height[i]: left_num;
            right_num = (height[n-1-i]>right_num)? height[n-1-i]: right_num;
            left[i] = left_num;
            right[n-1-i] = right_num;
        }
        
        for (int i=0; i<n; i++){
            sum_height += height[i];
            sum_water += min(left[i], right[i]);
        }
        return sum_water-sum_height;
    }

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.