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;
}
}
