Java solution with O(n)


  • 0
    G

    I am inspired by n00tc0d3r
    Here is my solution:

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

    Here is a simple explanation.
    Finding the largest container is same as finding the largest rectangle.
    The container with maximum volume must have a long bottom line, which might not be longest, and a tall cliff, which also might not be tallest.

    My idea is that we do not know the two tallest cliffs at the beginning.
    But we know the longest bottom line height.length-1. Thus, we can start with V0 = (height.length-1) * MIN(height[left],height[right]).

    If there is a container with greater volume than V0, called Vmax, it must have a larger height.
    In order to find Vmax, we need to find two large cliffs: height[left] and height[right].

    As the left cliff moving from left to right, only taller cliff might form a larger container, same as the right.


Log in to reply
 

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