Intuitive java loop with explanation


  • 1

    find the startIndex and endIndex where constructs the container, endIndex is a peak that height[end]>height[end-1]&&height[end]>=height[end+1].

    Especially, when height[endIndex]>=height[startIndex], we can directly compute, but if height[endIndex]<height[startIndex], we need to continue to find if there's some index j that height[j]>=height[startIndex].

    e.g: 4,1,0,3,2,4, we need to store index:3(because height[3]>height[2]&&height[3]>height[4]), and find index:5 which is equal to startIndex:0, otherwise if we stop at index:3, the result will be less than the correct answer.

    public class Solution {
        public int trap(int[] height) {
            int startIndex=-1;
            int tmpTop=-1;
            int water=0;
            for(int i=0;i<height.length;i++){
    
                if(i>0&&i<height.length-1&&height[i]>height[i-1]&&height[i]>=height[i+1]){    //find the temporary peak
                    if(startIndex==-1){ //find the start, e.g.: 0,0,1,2,0,5, so startIndex is 2
                        startIndex=i;
                    }else {
                        tmpTop=i;
                        for(int j=i;j<height.length;j++){
                        	if(height[j]>=height[startIndex]){  //find the true endIndex
                                tmpTop=j;
                                break;
                            }else if(height[j]>height[tmpTop]){   //update the endIndex if height[j]>height[tmpTop] but less than height[startIndex]
                                tmpTop=j;
                            }
                        }
                        water+=compute(height,startIndex,tmpTop);
                        startIndex=tmpTop;  //update the startIndex
                        i=tmpTop;
                    }
                }else if(i==0&&height.length>2&&height[0]>=height[1]){  //if startIndex is at the beginning,e.g.: 4,2,0,6
                    startIndex=0;
                }else if(i==height.length-1&&height.length>2&&height[i]>height[i-1]&&startIndex!=-1){
                    water+=compute(height,startIndex,i);  // e.g.: 4,2,0,6.  
               
                }
                
            }
            return water;
            
        }
        
        private int compute(int[]height,int start,int end){
            
            int level=Math.min(height[start],height[end]);
            int res=0;
            int i=start+1;
            while(i<end&&height[i]==height[i-1]){
            	i++;
            }
            for(;i<end;i++){
                if(height[i]<level){
            		res+=(level-height[i]);
            	}
            }
          
            return res;
        }
    }

Log in to reply
 

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