盛最多水的容器(中等)

題目

給定 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。

question_11.jpg

示例:

輸入: [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)的最大面積?；疑浅跏蓟瘯r(shí)填充的，不用管也用不到，填充順序按照 紅橙黃綠青 填充，填充 (0,1) 時(shí)選取 （0,0）和（1,1）和 area（0,1）中的最大值，area是求0和1組成的面積，以此類推（0,4）就是我們需要的。

tcHexo7y7j0zfsTY__thumbnail.jpg

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í)證明算法思想沒問題，也能求出來正確解。

但是，系統(tǒng)不給通過，系統(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 來持續(xù)存儲(chǔ)到目前為止所獲得的最大面積。 在每一步中，我們會(huì)找出指針?biāo)赶虻膬蓷l線段形成的區(qū)域，更新 maxarea

maxarea，并將指向較短線段的指針向較長(zhǎng)線段那端移動(dòng)一步。

最初我們考慮由最外圍兩條線段構(gòu)成的區(qū)域?，F(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;
    }
};