Java O(n) 8ms solution


  • 0
    P

    The way to approach this problem is using two pointers at the both end of the array, let's say L pointer and R pointer since the max area is actually determined by the smaller value of array[L] and array[R] and then multiple by the length which is R-L, therefore, when array[L] > array[R] we need to move the left pointer L to L+1, vice versa.

    public int maxArea(int[] height) {
            int[] h = height;
            if(h.length==0)
                return 0;
            if(h.length==2)
                return (h[1]-h[0])*Math.max(h[1],h[0]);
            int area=0;
            int len=0;
            int left=0;
            int right=h.length-1;
            int tempArea=0;
            while(left<right)
            {
                len=right-left;
                if(h[left]<h[right])
                {
                    tempArea=len*h[left];
                    left++;
                }
                else
                {
                    tempArea=len*h[right];
                    right--;
                }
                area=area>tempArea?area:tempArea;
            }
            return area;
    }

Log in to reply
 

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