Java o(n) one pass solution


  • 0
    L
    public class Solution {
    public int trap(int[] height) {
        int volume=0;
        int start=0;
        for(;start<height.length-1;){
           if(height[start]!=0){
               int mapSum=0;
               int cur=start+1;
               for(;cur<height.length&&height[cur]<height[start];cur++){
                   mapSum+=height[cur];//compute start to cur map sum volume
               }
               if(cur==height.length){//it indicates height[start] is Max in index from start to length-1
                   break;
               }
               else{
                   volume+=height[start]*(cur-start-1)-mapSum;//compute start to cur rain volume
                   start=cur;
               }
           }
           else start++;
        }
        if(start!=height.length-1){
           for(int end=height.length-1;end>start;){// compute from end to start like above method
               if(height[end]!=0){
                  int mapSum=0;
                  int cur=end-1;
                  for(;cur>=start&&height[cur]<height[end];cur--){
                     mapSum+=height[cur];
                  } 
                  if(cur==start-1) break;
                  else{
                      volume+=height[end]*(end-cur-1)-mapSum;
                      end=cur;
                  }
               }
               else end--;
           } 
        }
        return volume;
    }
    

    }


Log in to reply
 

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