11. 盛最多水的容器

給你 n 個非負(fù)整數(shù) a₁，a_2，...，a_n，每個數(shù)代表坐標(biāo)中的一個點(diǎn) (i, a_i) 。在坐標(biāo)內(nèi)畫 n 條垂直線，垂直線 i 的兩個端點(diǎn)分別為 (i, a_i) 和 (i, 0)。找出其中的兩條線，使得它們與 x 軸共同構(gòu)成的容器可以容納最多的水。
說明：你不能傾斜容器，且 n 的值至少為 2。
示例：
輸入：[1,8,6,2,5,4,8,3,7]
輸出：49

思路：

首先考慮面積怎么計算，如果只有兩個元素left,right，那么矩形的長等于兩個元素下標(biāo)的差right-left，矩形的高等于兩個元素小的那一個。那么怎么更新雙指針呢，更新兩個元素小的那一個。因?yàn)樾〉哪莻€元素決定了矩形的高，如果移動大的元素，矩形的長肯定會減一，而矩形的高只能小于或等于小的那個元素（新元素小于原小的元素），所以只要移動兩個元素中大的那個，矩形面積肯定會縮小。

class Solution {
public:
    int maxArea(vector<int>& height) {
        if(height.size()<2)
            return 0;
        int left=0,right=height.size()-1; //初始化左和右
        int maxarea=0; //記錄最大值
        while(left<right)
        {
            int hei=height[left]<height[right]?height[left]:height[right];  //矩形高為小的元素
            maxarea=hei*(right-left)>maxarea?hei*(right-left):maxarea; //更新面積
            if(hei==height[left]) //如果左小，則更新左
                ++left;
            else if(hei==height[right]) //如果右小，則更新右
                --right;
        }
        return maxarea;
    }
};

不能被示例[1,8,6,2,5,4,8,3,7]誤導(dǎo)，認(rèn)為height[left]==height[right]時最大面積就不會更新了，雖然這時長為最大，但是矩形面積等于長乘以高。如果中間有高特別高的，面積是有可能大于長最大的，比如{1, 3, 2, 5, 25, 24, 5}。