1.leetcode11-盛最多水的容器
題目描述
給定 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。
圖中垂直線代表輸入數(shù)組 [1,8,6,2,5,4,8,3,7]骡湖。在此情況下贱纠，容器能夠容納水（表示為藍(lán)色部分）的最大值為 49。
解題思路
矩陣的面積與兩個(gè)因素有關(guān)：矩陣的長度：兩條垂直線的距離响蕴；矩陣的寬度：兩條垂直線其中較短一條的長度
因此谆焊，要矩陣面積最大化，兩條垂直線的距離越遠(yuǎn)越好浦夷，兩條垂直線的最短長度也要越長越好辖试。
我們設(shè)置兩個(gè)指針 i 和 j，分別指向數(shù)組的最左端和最右端劈狐。此時(shí)罐孝，兩條垂直線的距離是最遠(yuǎn)的，若要下一個(gè)矩陣面積比當(dāng)前面積來得大肥缔，必須要把 height[i] 和 height[j] 中較短的垂直線往中間移動(dòng)莲兢，看看是否可以找到更長的垂直線。
代碼
class Solution {
public:
int maxArea(vector<int>& height) {
int res=0;
int i=0, j=height.size()-1;
while(i<=j){
res = max(res, (j-i)*min(height[i], height[j]));
if(height[i]<=height[j]) i++;
else j--;
}
return res;
}
};
