11. Container With Most Water

Given n non-negative integers a1, a2, ..., an, where each represents a point at coordinate (i, ai). n vertical lines are drawn such that the two endpoints of line i is at (i, ai) and (i, 0). Find two lines, which together with x-axis forms a container, such that the container contains the most water.
Note: You may not slant the container and n is at least 2.

Solution1：

思路：Two pointers from two ends，两端比较 小的移动，并每次compare and update max_area
Time Complexity: O(N) Space Complexity: O(1)

reference: kongweihan https://discuss.leetcode.com/topic/3462/yet-another-way-to-see-what-happens-in-the-o-n-algorithm

We start by computing the volume at (1,6), denoted by o. Now if the left line is shorter than the right line, then all the elements left to (1,6) on the first row have smaller volume, so we don't need to compute those cases (crossed by ---).

  1 2 3 4 5 6
1 x ------- o
2 x x
3 x x x 
4 x x x x
5 x x x x x
6 x x x x x x

Next we move the left line and compute (2,6). Now if the right line is shorter, all cases below (2,6) are eliminated.

  1 2 3 4 5 6
1 x ------- o
2 x x       o
3 x x x     |
4 x x x x   |
5 x x x x x |
6 x x x x x x

And no matter how this o path goes, we end up only need to find the max value on this path, which contains n-1 cases.

  1 2 3 4 5 6
1 x ------- o
2 x x - o o o
3 x x x o | |
4 x x x x | |
5 x x x x x |
6 x x x x x x

Solution2：Round1

Solution1 Code：

class Solution {
    public int maxArea(int[] height) {
        int max_area = 0;
        int start = 0, end = height.length - 1;
        while(start < end) {
            // update result
            int cur_max = Math.min(height[start], height[end]) * (end - start);
            if(cur_max > max_area)
                max_area = cur_max;
            
            // compare and move
            if(height[start] >= height[end]) {
                end--;
            }
            else {
                start++;
            }
        }
        return max_area;  
    }
}

Solution2 Round Code：

class Solution {
    public int maxArea(int[] height) {
        if(height == null || height.length == 0) return 0;
        int left = 0, right = height.length - 1;
        
        int max_area = Integer.MIN_VALUE;
        while(left < right) {
            int cur_area = Math.min(height[left], height[right]) * (right - left);
            max_area = Math.max(max_area, cur_area);
            if(height[left] <= height[right]) {
                left++;
            }
            else {
                right--;
            }
        }
        return max_area;
    }
}