Container With Most Water

Description

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 lineiis 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 1. Brute Force [Time Limit Exceeded]

public class Solution {
    public int maxArea(int[] height) {
        int[] idx = new int[2];
        int ma = 0;
        for(int i = 0; i < height.length; i++) {
            for(int j = i+1; j < height.length; j++) {
                int h = (height[i] > height[j]) ? height[j] : height[i];
                int w = j - i;
                int a = h * w;
                if(a > ma) {
                    ma = a;
                    idx[0] = i;
                    idx[1] = j;
                }
            }
        }
        return ma;
    }
}

Solution 2....

The maximum base we can get from the array is n-1, and the minimum height we can get is min(a1, a2, ..., an). So we can shrink the base while maintaining the maximum height between current two heights to get the max_area.

public class Solution {
    public int maxArea(int[] height) {
        int le = 0, ri = height.length - 1;
        int max = 0;
        while (le < ri) {
            int h = (height[le] > height[ri]) ? height[ri] : height[le];
            int w = ri - le;
            int area = h * w;
            if(area > max) max = area;
            if (height[le] > height[ri]) ri--;
            else le++;
        }
        return max;
    }
}