Problem Description

You are given an integer array height of length n. There are n vertical lines drawn such that the two endpoints of the ith line are (i, 0) and (i, height[i]).

Find two lines that together with the x-axis form a container, such that the container contains the most water.

Return the maximum amount of water a container can store.

Notice that you may not slant the container.

Example 1

Input: height = [1,8,6,2,5,4,8,3,7]
Output: 49
Explanation: The above vertical lines are represented by array [1,8,6,2,5,4,8,3,7]. In this case, the max area of water (blue section) the container can contain is 49.

Solution

There are two degrees of freedom, and the problem asks to maximize an objective function of these two variables. There're different ways to view the problem, either we set two variables as the left position and right position of the container, or we can think of the width and the height of the container as two variables. The width and height are better variables since they are directly related to the capacity of the container. Further, we can easily implement the greedy algo. on them.

To start, we maximize one variable, which should be the width in this case. Given n-size array, the max width is n-1 and there is only one such container. To explore the variables' space, the next step is to search all containers with width equal to n-2, and then n-3, etc. Now the key is the iteration, how we move from n-1 to n-2? We do not want to really calculate capacities of all containers with width n-2, in fact, we only want to calculate the n-2-width container which at least hopefully has larger volume. Given the n-1-width container, we have the simple choice to move either one side to shrink the width by 1. And also we only want to move the shorter side, in the hope to find a larger container. In the case of the equal sides, we can move them both, since moving either one side cannot increase the volume for sure.

Java Code

class Solution {
    public int maxArea(int[] height) {
        int n = height.length, l=0, r=n-1, ma=0;
        while(l<r){
            ma = Math.max(ma, (r-l)*Math.min(height[l], height[r]));
            if( height[l]>height[r] ) r--;
            else if( height[l]<height[r] ) l++;
            else {r--; l++;};
        }
        return ma;
    }
}