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:

如果用暴力解法則復(fù)雜度為 O(n^2)?？戳?tag 居然有 Two pointers，但感覺用 two pointers 從兩端朝中間移動(dòng)并不能保證朝著最大值不斷遞增增長。但看了discuss 發(fā)現(xiàn)其實(shí)并不需要不斷遞增，只需要保證可以取道最大值時(shí)的情況就可以了。因此可以用 two pointers 來做，每次移動(dòng)較短的那一邊一定可以取到最大值，證明如下：

假設(shè)當(dāng)前左右兩個(gè)指針為 i，j，當(dāng)前對應(yīng)的值為 height[i] 和 height[j], 面積為 Math.min(height[i], height[j]) * (j - i)。當(dāng) height[i] < height[j]時(shí)，如果移動(dòng)較長的邊 j = j - 1，則新的面積的值永遠(yuǎn)不可能大于之前得到的面積，（因?yàn)槿莘e由較短邊決定），而如果移動(dòng)較短邊，則新的面積有可能大于之前得到的面積(最短邊可能變長甚至超過較長邊)。

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