Simple Java Code beats 90% by finding raising subsequences


  • 0
            public int trap(int[] height) {
    		int len = height.length;
    		if (len==0) return 0;
    		int max = height[0], sum = 0, max_index = 0, i = 0;
    		// from left to right
    		while (i<len) {
    			while (i>0 && i<=len-1 && height[i]==height[i-1])
    				i++;
    			if (i == len) break;
    			if (height[i]>=max) {
    				//add to sum and update max info
    				for (int j=max_index; j<i; j++) {
    					sum += max-height[j];
    					height[j] = max; 
                                            //this line is necessary, otherwise input like [3,0,3,0,3,0,3] will be counted again from right to left 
    				}
    				max = height[i];
    				max_index = i;
    			}
    			i++;
    		}
    		// from right to left
    		i = len-1; max = height[i]; max_index = i;
    		while (i>=0) {
    			while (i>=0 && i<len-1 && height[i]==height[i+1])
    				i--;
    			if (i<0) break;
    			if (height[i]>=max) {
    				//add to sum and update max info
    				for (int j=max_index; j>i; j--)
    					sum += max-height[j];
    				max = height[i];
    				max_index = i;
    			}
    			i--;
    		}
    		return sum;

Log in to reply
 

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