11. Container With Most Water

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.

Solution

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