LeetCode第十一題
題目描述：
給你 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
來(lái)源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/container-with-most-water
思路
第一種：直接簡(jiǎn)單暴力法波附，兩層循環(huán)，時(shí)間復(fù)雜度為平方級(jí)別
第二種：首尾雙指針?lè)ㄖ缱辍．?dāng)初始兩個(gè)指針指向首尾時(shí)掸屡，底部為最大值。此時(shí)指針的移動(dòng)有兩種方式然评，一個(gè)是將左指針增大仅财，一個(gè)是將右指針減少。不管是哪一種碗淌，底部都要減1盏求，而高取的是左右中小的那個(gè)值。所以應(yīng)該不能將高的那個(gè)指針移動(dòng)亿眠，應(yīng)該移動(dòng)較小的那個(gè)值的指針碎罚。
源代碼
//方法一：暴力法
int min(int num1,int num2){
if(num1 < num2)
return num1;
else
return num2;
}
int maxArea(int* height, int heightSize){
int v_max = 0;
int volume;
for(int i = 0;i < heightSize - 1;++i){
for(int j = i + 1;j < heightSize;++j){
volume = (j - i) * min(height[j],height[i]);
if(volume > v_max)
v_max = volume;
}
}
return v_max;
}
//方法二：雙指針?lè)?int min(int num1,int num2){
if(num1 < num2)
return num1;
else
return num2;
}
int maxArea(int* height, int heightSize){
int left = 0;
int right = heightSize - 1;
int v_max = 0;
int volume;
while(left < right){
volume = (right - left) * min(height[left],height[right]);
if(volume > v_max)
v_max = volume;
if(height[left] < height[right])
++left;
else
--right;
}
return v_max;
}
分析
采用雙指針?lè)〞r(shí)間復(fù)雜度為線性級(jí)別，空間復(fù)雜度為常數(shù)級(jí)別纳像。
