給你 n 個非負整數(shù) a1，a2，...，an，每個數(shù)代表坐標中的一個點 (i, ai) 。在坐標內(nèi)畫 n 條垂直線，垂直線 i 的兩個端點分別為 (i, ai) 和 (i, 0)。找出其中的兩條線，使得它們與 x 軸共同構(gòu)成的容器可以容納最多的水。

說明：你不能傾斜容器，且 n 的值至少為 2。

image.png

圖中垂直線代表輸入數(shù)組 [1,8,6,2,5,4,8,3,7]。在此情況下，容器能夠容納水（表示為藍色部分）的最大值為 49。

示例：

輸入：[1,8,6,2,5,4,8,3,7]
輸出：49

解題思路

首先需要抽象出題目的數(shù)學(xué)模型，容器可以容納的水也就是求矩形的面積，矩形的底可以通過數(shù)組下標來確定：j - i，高度由 最短的邊決定，所以公式可以表示為：res = ( j - i ) * Math.min(height[j] , height[i]);

思路1：
暴力破解法，兩層循環(huán)逐個遍歷所有矩形，找出最大面積的矩形。
時間復(fù)雜度O(n*n),空間復(fù)雜度O(1)。

class Solution {

    public int maxArea(int[] height) {

        int max = Integer.MIN_VALUE;
        for(int i=0;i<height.length;i++)
        {
            for(int j=i+1;j<height.length;j++)
            {
                int val = (j-i) * Math.min(height[i],height[j]);
                max = Math.max(max,val);
            }
        }
        return max;
    }
}

運算結(jié)果：執(zhí)行用時 :639 ms 內(nèi)存消耗 :39.6 MB

思路2：
雙指針，左右指針分別位于數(shù)組的始末位置，按照約定的規(guī)則移動指針直到兩個指針重合，找到最大的矩形。

下面我們就要討論下該如何移動指針：假設(shè)我們兩個指針分別指向x和y，假設(shè) x <= y ,間距為t，矩形的面積：min（x，y）* t
我們?nèi)我庀蜃笠苿佑抑羔樀統(tǒng)1，兩指針之間的間距t1，顯然t1 < t 并且
如果y1 <= y ,那么 min(x , y1) <= min(x , y)
如果y1 > y ,那么 min(x , y1) = x = min(x , y)
我們有 ： min(x , y') * t' <= min(x,y)*t
所以不論怎么移動y，矩形的面積都不會大于之前的面積，也就是說移動較大的一邊沒有任何意義，我們每移動一次重新找到小的一邊接著移動即可。

public int maxArea(int[] height) {

        int left = 0;
        int right = height.length-1;

        int max = 0;
        while(left < right)
        {
            if(height[left] <= height[right])
            {
                max = Math.max(max,(right-left) * height[left++]);
            }else
            {
                max = Math.max(max,(right-left) *height[right--]);
            }
        }

運算結(jié)果：執(zhí)行用時 :3 ms 內(nèi)存消耗 :39.4 MB

綜上采用方法2.