昨晚難得忙的差不多驮履，自己有點(diǎn)時(shí)間惭蟋，做了道中等難度的題
題目—LeetCode盛最多水的容器
給定 n 個(gè)非負(fù)整數(shù) a1，a2逼泣，...趴泌，an，每個(gè)數(shù)代表坐標(biāo)中的一個(gè)點(diǎn) (i, ai) 拉庶。在坐標(biāo)內(nèi)畫(huà) n 條垂直線嗜憔，垂直線 i 的兩個(gè)端點(diǎn)分別為 (i, ai) 和 (i, 0)。找出其中的兩條線氏仗，使得它們與 x 軸共同構(gòu)成的容器可以容納最多的水吉捶。
示例圖片
圖中垂直線代表輸入數(shù)組 [1,8,6,2,5,4,8,3,7]。在此情況下皆尔，容器能夠容納水（表示為藍(lán)色部分）的最大值為 49呐舔。
- 示例
輸入: [1,8,6,2,5,4,8,3,7]
輸出: 49
以上題目描述就照搬原文了
思路
-
思路一：暴力法
首先，這道題最容易想到的就是暴力法慷蠕，即計(jì)算每?jī)蓚€(gè)之間的盛水量滋早，1和之后的每一個(gè)比較，2和之后的每一個(gè)比較砌们，n-1和n比較，即k不和k-1比較搁进。這樣結(jié)果肯定是能得到的浪感，但是效率不言而喻，若出現(xiàn)在筆試題中饼问，肯定時(shí)間等過(guò)不了影兽。
來(lái)分析一下暴力法的時(shí)間復(fù)雜度：- 第一個(gè)數(shù)和后面n-1個(gè)數(shù)比較，次數(shù)為(n-1)莱革。
- 第二個(gè)數(shù)和后面n-2個(gè)數(shù)比較峻堰，次數(shù)為(n-2)。
- ......
- 第n-1個(gè)數(shù)和后面
第n個(gè)數(shù)比較盅视，次數(shù)為n-(n-1)捐名。
，（還去查了一下等差數(shù)列求和闹击，手動(dòng)捂臉）因此時(shí)間復(fù)雜度為
-
思路二：雙指針?lè)?br> 通常在涉及到數(shù)組遍歷時(shí)镶蹋，能在一次遍歷找到結(jié)果，是最好的結(jié)局，題目需要的是兩個(gè)下標(biāo)的數(shù)字去求解結(jié)果贺归，因此想到雙指針的方案淆两，
從左到右i，和從右到左j拂酣。那么問(wèn)題就在于如何移動(dòng)下標(biāo)秋冰？其實(shí)很容易，當(dāng)然是移動(dòng)下標(biāo)處值較小的下標(biāo)婶熬。
來(lái)分析一下時(shí)間復(fù)雜度：- 無(wú)論是左下標(biāo)移動(dòng)還是右下標(biāo)移動(dòng)剑勾，最后都只會(huì)遍歷一遍數(shù)組，因此時(shí)間復(fù)雜度為
- 無(wú)論是左下標(biāo)移動(dòng)還是右下標(biāo)移動(dòng)剑勾，最后都只會(huì)遍歷一遍數(shù)組，因此時(shí)間復(fù)雜度為
實(shí)現(xiàn)（java）
- 思路一：暴力法
public static int maxArea(int[] height) {
int maxWater = 0;
for(int i = 0; i < height.length -1; i++) {
for(int j = i+1; j < height.length; j++) {
int higth = height[i] < height[j] ? height[i] : height[j];
int tempWater = higth * (j - i);
if(maxWater < tempWater)
maxWater = tempWater;
}
}
return maxWater;
}
- 思路二：雙指針?lè)?/li>
public static int maxArea2(int[] height) {
int maxWater = 0;
int i = 0, j = height.length - 1;
int hight = 0;
int temp = 0;
while(i != j) {
hight = height[i] < height[j] ? height[i] : height[j];
temp = hight * (j - i);
if(temp > maxWater)
maxWater = temp;
if(height[i] <= height[j]) {
i++;
} else {
j--;
}
}
return maxWater;
}
在上面方法中尸诽，沒(méi)有用到Java的Math類甥材，主要是之前聽(tīng)人說(shuō)，這些類的使用會(huì)使得運(yùn)行時(shí)間變長(zhǎng)性含。所以我為了驗(yàn)證洲赵，就有了下面的方法
public static int maxArea3(int[] height) {
int maxWater = 0;
int i = 0, j = height.length - 1;
while(i != j) {
maxWater = Math.max(maxWater, Math.min(height[i], height[j]) * (j - i));
if(height[i] <= height[j]){
i++;
}
else{
j--;
}
}
return maxWater;
}
那么暴力法究竟效率有多低，使用Math類的處理商蕴，又和沒(méi)用Math類的處理方法有何區(qū)別叠萍？直接上圖。
對(duì)比發(fā)現(xiàn)：
- 暴力法確實(shí)效率低绪商。
- 使用Math類并不會(huì)使得效率有多大的改變苛谷，所以以后可以使用這些數(shù)學(xué)類，減少代碼格郁。
最后
此致腹殿，敬禮
