*Java* 3ms solution with step-by-step explanations (beats 85%)


  • 30
    E

    It took me quite some time to finally optimize my solution from 21ms to 3ms :(

    If you have difficulty understanding the following code, check this link for a detailed explanation.

    public int maxArea(int[] height) {
        int L = height.length, lo = 0, hi = L-1;
        int max = 0;
        while(lo<hi) {	  
            int loMax = height[lo], hiMax = height[hi];      
    
        	int candidate = (hi-lo) * (loMax<hiMax ? loMax : hiMax);
        	max = candidate > max ? candidate : max;
    
        	if(height[lo]<=height[hi]) 
        	    while(lo<hi && height[lo]<=loMax) ++lo; 
        	else 
        	    while(hi>lo && height[hi]<=hiMax) --hi;
        }
        return max;
    }
    

  • 0
    X

    Sweeeeeeeeeeet!


  • 0
    W

    Great solution!


  • 1
    J

    lo < hi * 2 and height[lo] <= height[hi] * 2,
    not batter,
    This is my answer

    public class Solution {
    public int maxArea(int[] height) {
        int left = 0;
    	int right = height.length-1;
    	int max = 0,temp = 0;
    	while(left<right) {
    		if(height[left] > height[right]){
    			temp = (right-left) * height[right];
    			right--;
    		}else{
    			temp = (right-left) * height[left];
    			left++;
    		}
    		max = max > temp ? max :temp;
    	}
    	return max;
       }
    }

  • 0
    D

    Great solution with explanation!


  • 0
    E

    @james_shu_sunlin more clear for me, thanks!


  • 0
    J

  • 0
    C

    Simple way

    public int maxArea(int[] height) {
            int max = 0;
            int i = 0;
            int j = height.length - 1;
            while (i < j) {
                int loMax = height[i];
                int hiMax = height[j];
                max = Math.max(Math.min(height[i], height[j]) * (j - i), max);
    
                // without this, TLE will occur
                if (height[i] <= height[j])
                    while (i < j && height[i] <= loMax) ++i;
                else
                    while (i < j && height[j] <= hiMax) --j;
            }
    
            return max;
        }
    

Log in to reply
 

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