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:

如果用暴力解法则复杂度为 O(n^2)。看了 tag 居然有 Two pointers，但感觉用 two pointers 从两端朝中间移动并不能保证朝着最大值不断递增增长。但看了discuss 发现其实并不需要不断递增，只需要保证可以取道最大值时的情况就可以了。因此可以用 two pointers 来做，每次移动较短的那一边一定可以取到最大值，证明如下：

假设当前左右两个指针为 i，j，当前对应的值为 height[i] 和 height[j], 面积为 Math.min(height[i], height[j]) * (j - i)。当 height[i] < height[j]时，如果移动较长的边 j = j - 1，则新的面积的值永远不可能大于之前得到的面积，（因为容积由较短边决定），而如果移动较短边，则新的面积有可能大于之前得到的面积(最短边可能变长甚至超过较长边)。

code：

public class Solution 
{
    public int maxArea(int[] height) 
    {
        int maxArea = 0;
        int length = height.length;
        int i = 0, j = length - 1;
        while(i < j)
        {
            int curArea = Math.min(height[i], height[j]) * (j - i);
            if(curArea > maxArea)
                maxArea = curArea;
            if(height[i] > height[j])
                j --;
            else
                i ++;
        }
        return maxArea;
    }
}