42. Trapping Rain Water

problem description

Given n non-negative integers representing an elevation map where the width of each bar is 1, compute how much water it is able to trap after raining.

The above elevation map is represented by array [0,1,0,2,1,0,1,3,2,1,2,1]. In this case, 6 units of rain water (blue section) are being trapped. Thanks Marcos for contributing this image!

Example:

Input: [0,1,0,2,1,0,1,3,2,1,2,1]
Output: 6

algorithm thought

和之前一个接水的题目异曲同工，使用左右指针结题。哪边短，动哪边，最后两指针重合退出循环。中间维护左右相应的最大值，存水量等于最大值减去当前值。

code

class Solution {
public:
    int trap(vector<int>& height) {
        if(height.size()==0)
            return 0;
        int left=0;
        int right=height.size()-1;
        int leftmax=height[left];
        int rightmax=height[right];
        int res=0;
        while(left<right){
           // cout<<left<<'-'<<right<<' ';
            if(height[left]<height[right]){
                
                if(height[left]<=leftmax){
                    res+=leftmax-height[left++];
                }else{
                    leftmax=height[left];
                }
                
            }else{
                
                if(height[right]<=rightmax){
                    res+=rightmax-height[right--];
                }else{
                    rightmax=height[right];
                }
                
            }
        }
        return res;
    }
};

algorithm thought

一个循环左右指针逼近，时间复杂度O(n)。