C++ O(n) time O(1) space 9ms solution


  • 0

    From beginning, find the next bar which is higher than the current bar, calculate the total water, do it recursively till end.

        int trap(vector<int>& height) {
            if(height.size()==0) return 0;
            return trapHelper(height,0);
        }
        
        int trapHelper(vector<int>& height,int begin){
            if(begin>=height.size()-1) return 0;
            while(height[begin+1]>=height[begin]) begin++;
            if(begin>=height.size()-1) return 0;
            int i=begin+1;
            int maxHeight=-1;
            int maxAt=0;
            while(height[i]<height[begin]&&i<height.size()){
                if(height[i]>maxHeight){
                    maxHeight=height[i];
                    maxAt=i;
                }
                i++;
            }
            if(i<height.size()) return calArea(height,begin,i,height[begin])+trapHelper(height,i);
            else return calArea(height,begin,maxAt,maxHeight)+trapHelper(height,maxAt);
        }
        
        int calArea(vector<int>& height,int begin,int end,int maxHeight){
            int sum=0;
            for(int i=begin+1;i<end;i++)
                sum+=maxHeight-height[i];
            return sum;
        }
    

Log in to reply
 

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