給你 n 個非負(fù)整數(shù) a1填硕，a2麦萤，...，an廷支，每個數(shù)代表坐標(biāo)中的一個點 (i, ai) 。在坐標(biāo)內(nèi)畫 n 條垂直線栓辜，垂直線 i 的兩個端點分別為 (i, ai) 和 (i, 0)恋拍。找出其中的兩條線，使得它們與 x 軸共同構(gòu)成的容器可以容納最多的水藕甩。
說明：你不能傾斜容器施敢，且 n 的值至少為 2。
圖中垂直線代表輸入數(shù)組 [1,8,6,2,5,4,8,3,7]狭莱。在此情況下僵娃，容器能夠容納水（表示為藍(lán)色部分）的最大值為 49。
示例：
輸入：[1,8,6,2,5,4,8,3,7]
輸出：49
解題思路
首先需要抽象出題目的數(shù)學(xué)模型腋妙，容器可以容納的水也就是求矩形的面積默怨，矩形的底可以通過數(shù)組下標(biāo)來確定：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.
