題目

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

題目

分析

這道題本身并不是很難（其實(shí)我跳過了一題，第十題，實(shí)在是有點(diǎn)智商不夠）

• 解法1：暴力算法
  兩層for循環(huán)從頭算到尾，提交后擊敗了0.00%的玩家····這個(gè)我就不多討論了···

• 解法2：分析一下矩形面積與長(zhǎng)和寬相關(guān)，我們不妨讓寬為最大，即取數(shù)組兩端(a[0],a[lenght-1])，那么高即為min(a[0],a[lenght-1]),那么我們下組長(zhǎng)寬如何去選取呢？其實(shí)很簡(jiǎn)單，我們將某一端向內(nèi)移動(dòng)一位，那么是哪一端呢？當(dāng)然是選擇短的一端移動(dòng)才有可能得到大的，即：
  如果 a[0]>a[length-1]=>a[0],a[length-2];
  否則 a[0]<a[length-1]=>a[1],a[length-1];
  思路清晰了就可以coding了。

    public int maxArea(int[] height) {
        int res=0;
        int l=0;
        int r=height.length-1;
        while(l!=r){
            res=Math.max(res,Math.min(height[l],height[r])*(r-l));
            if(height[l]>height[r]){
                r--;
            }else{
                l++;
            }
        }
        return res;
    }

提交一下，測(cè)試用例耗時(shí)由幾百毫秒降至8毫秒~~