給你 n 個非負(fù)整數(shù) a1，a2，...，an，每個數(shù)代表坐標(biāo)中的一個點(diǎn) (i, ai) 。在坐標(biāo)內(nèi)畫 n 條垂直線，垂直線 i 的兩個端點(diǎn)分別為 (i, ai) 和 (i, 0)。找出其中的兩條線，使得它們與 x 軸共同構(gòu)成的容器可以容納最多的水。說明：你不能傾斜容器，且 n 的值至少為 2。

快速一欄:

1. 暴力拆解
2. 雙指針

感覺自己進(jìn)步很大，第一反應(yīng)就是雙指針，但是對雙指針的移動條件不是很明確，所以先上一輪暴力解法，時間復(fù)雜度O（N2）,空間復(fù)雜度O（N）。

整體思路是在以i開頭的所有框中找到最大的存入max[i]中，依次遞推，再在max[i]中找最大值，簡單粗暴，實際上也AC了：

    public int maxArea(int[] height) {
        int len = height.length;
        int[] max = new int[len];
        for(int i = 0; i < len; i ++) {
            for(int j = i + 1; j < len; j ++) {
                if((j - i) * Math.min(height[i], height[j]) > max[i])
                    max[i] = (j - i) * Math.min(height[i], height[j]);
            }
        }
        int res = 0;
        for(int val : max) {
            if(res < val)
                res = val;
        }
        return res;
    }

當(dāng)然，跑完的成績并不優(yōu)秀，再回到雙指針的方法，雙指針基本思想是：從兩端開始，計算由left和right構(gòu)成的矩形，之后將其中較矮的那邊向?qū)?cè)移動一格。原理是把不可能的選項排除掉。

假設(shè)我們把高的那個移動若干格，矮的不動，很容易理解得到的結(jié)果一定小于初始矩形的面積。所以雖然不知道高邊不動的結(jié)果是是不是最優(yōu)解，但矮邊不動高邊動的結(jié)果一定不是，所以可以排除。

public int maxArea(int[] height) {
        int max = 0;
        int left = 0;
        int right = height.length - 1;//雙指針
        while(left < right) {
            int temp = (right - left) * (Math.min(height[left], height[right]));
            if(temp > max)
                max = temp;
            if(height[left] < height[right])
                left ++;
            else
                right --;
        }
        return max;
    }