1.題目描述
? 給定 n 個(gè)非負(fù)整數(shù) 
，
幻工，...励两，
，每個(gè)數(shù)代表坐標(biāo)中的一個(gè)點(diǎn) (i, 
) 囊颅。在坐標(biāo)內(nèi)畫 n 條垂直線当悔，垂直線 i 的兩個(gè)端點(diǎn)分別為 (i, ) 和 (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
2.提交記錄
11.暴力枚舉法.png
11.雙指針法.png
3.算法思想
這道題目的意思是在輸入的int *height中宏多，找到兩個(gè)數(shù)字使得他們?cè)谧鴺?biāo)軸上圍成的面積最大。
方法一：暴力枚舉法澡罚。
使用兩層循環(huán)伸但，對(duì)每種可能進(jìn)行暴力枚舉。但是這種方法使得時(shí)間復(fù)雜度較高留搔，速度較慢更胖。
方法二：雙指針法。
為了降低時(shí)間復(fù)雜度，我們?cè)谟删€段長(zhǎng)度構(gòu)成的數(shù)組中使用兩個(gè)指針却妨，一個(gè)放在開始饵逐，一個(gè)置于末尾，即定義兩個(gè)整型指針 left 和 right 彪标，使得left = 0倍权；right = heightSize - 1。
由題意得捞烟，面積的初始值為*(height + left) * (right -left)薄声。為了確保面積最大，我們會(huì)找出兩個(gè)指針?biāo)赶虻膬蓷l線段形成的區(qū)域题画，持續(xù)更新最大面積默辨，每次 *(height + left) 和 *(height + right) 值較小的一方，都要往數(shù)組中間移動(dòng)一步苍息。
4.實(shí)現(xiàn)過程
int maxArea(int* height, int heightSize){
int max = 0,temp = 0;
for(int i = 0;i < heightSize-1;i++){
for(int j = i+1;j < heightSize;j++){
if(*(height+i) < *(height+j)){
temp = (*(height+i) * (j-i)) ;
}else{
temp = (*(height+j) * (j-i)) ;
}
if(max < temp){ max = temp; }
}
}
return max;
}
int maxArea(int* height, int heightSize){
int left = 0 , right = heightSize - 1;
int max = 0,temp = 0;
while(left < right){
if( *(height + left) < *(height + right) ){
temp = *(height + left) * (right - left) ;
left++;
}else{
temp = *(height + right) * (right - left) ;
right--;
}
if(max < temp){ max = temp; }
}
return max;
}
5.復(fù)雜度分析
- 時(shí)間復(fù)雜度：O(n2)缩幸；
- 空間復(fù)雜度：O(1)；
- 時(shí)間復(fù)雜度：O(n)竞思；
- 空間復(fù)雜度：O(1)表谊；
