盛最多水的容器(中等)
題目
給定 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)成的容器可以容納最多的水郎仆。
說(shuō)明：你不能傾斜容器，且 n 的值至少為 2兜蠕。
示例:
輸入: [1,8,6,2,5,4,8,3,7]
輸出: 49
思路
利用動(dòng)態(tài)規(guī)劃扰肌，創(chuàng)建一個(gè)9*9的二維數(shù)組，如下圖熊杨，（x,y）存儲(chǔ)的是曙旭，x到y(tǒng)范圍內(nèi)的最大面積『锇迹灰色是初始化時(shí)填充的夷狰，不用管也用不到，填充順序按照 紅橙黃綠青 填充郊霎，填充 (0,1) 時(shí)選取 （0,0）和（1,1）和 area（0,1）中的最大值沼头，area是求0和1組成的面積，以此類推（0,4）就是我們需要的书劝。
c++代碼（動(dòng)態(tài)規(guī)劃）
class Solution {
public:
int area(vector<int>& in,int left,int right){
int area = min(in[left],in[right]) * (right-left);
return area;
}
int maxArea(vector<int>& height) {
int length = height.size();
//這個(gè)是動(dòng)態(tài)創(chuàng)建指定長(zhǎng)度二維數(shù)組
//int ** list;
//list = new int *[length+1];
//for(int i = 0; i < length+1; i ++)
//list[i] = new int[length+1];
//靜態(tài)創(chuàng)建list數(shù)組
int list[1000][1000] = {0};
for(int x = 1;x < length;++x){
for(int y = 0;y + x < length; ++y){
list[y][x+y] = max(max(list[y][x+y-1],list[y+1][x+y]),area(height,y,x+y));
}
}
return list[0][length-1];
}
};
至此进倍，證畢。事實(shí)證明算法思想沒(méi)問(wèn)題购对，也能求出來(lái)正確解猾昆。
但是，系統(tǒng)不給通過(guò)骡苞，系統(tǒng)測(cè)試用例給了5000長(zhǎng)的數(shù)組垂蜗，不管是動(dòng)態(tài)創(chuàng)建還是靜態(tài)創(chuàng)建二維數(shù)組，都會(huì)棧溢出解幽。
c++代碼（雙指針）
這種方法背后的思路在于贴见，兩線段之間形成的區(qū)域總是會(huì)受到其中較短那條長(zhǎng)度的限制。此外躲株，兩線段距離越遠(yuǎn)片部，得到的面積就越大。
我們?cè)谟删€段長(zhǎng)度構(gòu)成的數(shù)組中使用兩個(gè)指針霜定，一個(gè)放在開始档悠，一個(gè)置于末尾廊鸥。 此外，我們會(huì)使用變量 maxarea
maxarea 來(lái)持續(xù)存儲(chǔ)到目前為止所獲得的最大面積辖所。 在每一步中惰说，我們會(huì)找出指針?biāo)赶虻膬蓷l線段形成的區(qū)域，更新 maxarea
maxarea奴烙，并將指向較短線段的指針向較長(zhǎng)線段那端移動(dòng)一步助被。
最初我們考慮由最外圍兩條線段構(gòu)成的區(qū)域∑收牛現(xiàn)在切诀，為了使面積最大化，我們需要考慮更長(zhǎng)的兩條線段之間的區(qū)域搔弄。如果我們?cè)噲D將指向較長(zhǎng)線段的指針向內(nèi)側(cè)移動(dòng)幅虑，矩形區(qū)域的面積將受限于較短的線段而不會(huì)獲得任何增加。但是顾犹，在同樣的條件下倒庵，移動(dòng)指向較短線段的指針盡管造成了矩形寬度的減小，但卻可能會(huì)有助于面積的增大炫刷。因?yàn)橐苿?dòng)較短線段的指針會(huì)得到一條相對(duì)較長(zhǎng)的線段擎宝，這可以克服由寬度減小而引起的面積減小。
class Solution {
public:
int maxArea(vector<int>& height) {
int left = 0; //左指針
int right = height.size()-1; //右指針
int maxarea = 0;
while(left != right){
maxarea = max(min(height[left],height[right]) * (right-left) , maxarea);
(height[left] < height[right]) ? ++left : --right;
}
return maxarea;
}
};
