大家好,我是吳師兄,
今天的題目來源于 LeetCode 第 11 號(hào)問題:盛最多水的容器,難度為「中等」,屬于雙指針的經(jīng)典題目。
一、題目描述
給你 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)成的容器可以容納最多的水。
二、題目解析
一開始,我們先去考慮相距最遠(yuǎn)的兩個(gè)柱子所能容納水的面積。

接下來去思考,我們?nèi)ヒ苿?dòng)哪根柱子會(huì)更加合適?
這里我們需要注意一點(diǎn):無論移動(dòng)哪根柱子,柱子之間的寬度都是變小的。
移動(dòng)右邊那根更高的柱子?


由于水面高度是由最短的柱子決定的,所以移動(dòng)右邊那根更高的柱子的時(shí)候,水面高度一定是不會(huì)增加,甚至有可能遇到更短的柱子而變小,而寬度有一定再減少,所以水的面積也一定減少。
移動(dòng)左邊那根更短的柱子?
這時(shí)候,水的高度是不確定的,那么面積也是不確定的,有可能比之前更大,也有可能更小或者相等。
所以,我們可以得出一個(gè)結(jié)論:移動(dòng)兩根柱子之間更短的那根柱子,才有可能在寬度一定變小的情況下,找到一個(gè)更高的水面,從而使得面積有可能更大。
那接下來這道題目的解法也就有了:
1、設(shè)置兩個(gè)索引,分別指向容器的兩側(cè),即索引left指向最左邊的柱子,索引right指向最右邊的柱子。

2、記錄下此時(shí)的水的面積,可以定義為 res
3、觀察需要向內(nèi)移動(dòng)哪根柱子
- 1)如果移動(dòng)較高的柱子,由于水的寬度在變小,而水的高度一定不會(huì)增加,所以最終水的面積不會(huì)超過之前記錄的水的面積 res
- 2)所以,只能移動(dòng)較短的柱子,然后計(jì)算此時(shí)水的面積,再與之前記錄的水的面積 res 進(jìn)行比較,保存那個(gè)更大的值
4、再去判斷應(yīng)該向內(nèi)移動(dòng)哪根柱子
5、直到left和right相遇為止
三、參考代碼
1、Java 代碼
//登錄AlgoMooc官網(wǎng)獲取更多算法圖解
//https://www.algomooc.com/587.html
//作者:程序員吳師兄
//代碼有看不懂的地方一定要私聊咨詢吳師兄呀
//盛最多水的容器(LeetCode11):https://leetcode-cn.com/problems/container-with-most-water/
classSolution{
publicintmaxArea(int[]height){
//設(shè)置兩個(gè)索引,分別指向容器的兩側(cè)
//索引left指向最左邊的柱子
intleft=0;
//索引right指向最右邊的柱子
intright=height.length-1;
//設(shè)置一個(gè)變量用來保存當(dāng)下水的最大面積
intres=0;
//移動(dòng)left和right,直到left和right相遇為止
while(left//水的寬度是right-left
intwidth=right-left;
//水的高度由兩根柱子最短的那根決定
inth=Math.min(height[left],height[right]);
//計(jì)算此時(shí)水的面積
intarea=width*h;
//如果此時(shí)水的面積大于了我們之前保存的那個(gè)值,我們需要更新一下
if(area>=res){
//更新res的值為area,確保res一直都是最大的值
res=area;
}
//接下來去觀察需要移動(dòng)哪根柱子:必定是最短的那根柱子
//如果左邊的柱子更短,那么向內(nèi)移動(dòng)左邊的柱子,因?yàn)橹挥羞@樣,才有可能找到一個(gè)更高的水面
//在寬度一定變小的情況下,水的面積才有可能增大
if(height[left]//向內(nèi)移動(dòng)左邊的柱子
left++;
//如果右邊的柱子更短,那么向內(nèi)移動(dòng)右邊的柱子,因?yàn)橹挥羞@樣,才有可能找到一個(gè)更高的水面
//在寬度一定變小的情況下,水的面積才有可能增大
}else{
//向內(nèi)移動(dòng)右邊的柱子
right--;
}
}
//最后返回最大的面積res即可
returnres;
}
}
2、C++ 代碼
//登錄AlgoMooc官網(wǎng)獲取更多算法圖解
//https://www.algomooc.com/587.html
//作者:程序員吳師兄
//代碼有看不懂的地方一定要私聊咨詢吳師兄呀
//盛最多水的容器(LeetCode11):https://leetcode-cn.com/problems/container-with-most-water/
classSolution{
public:
intmaxArea(vector<int>&height){
//設(shè)置兩個(gè)索引,分別指向容器的兩側(cè)
//索引left指向最左邊的柱子
intleft=0;
//索引right指向最右邊的柱子
intright=height.size()-1;
//設(shè)置一個(gè)變量用來保存當(dāng)下水的最大面積
intres=0;
//移動(dòng)left和right,直到left和right相遇為止
while(left//水的寬度是right-left
intwidth=right-left;
//水的高度由兩根柱子最短的那根決定
inth=min(height[left],height[right]);
//計(jì)算此時(shí)水的面積
intarea=width*h;
//如果此時(shí)水的面積大于了我們之前保存的那個(gè)值,我們需要更新一下
if(area>=res){
//更新res的值為area,確保res一直都是最大的值
res=area;
}
//接下來去觀察需要移動(dòng)哪根柱子:必定是最短的那根柱子
//如果左邊的柱子更短,那么向內(nèi)移動(dòng)左邊的柱子,因?yàn)橹挥羞@樣,才有可能找到一個(gè)更高的水面
//在寬度一定變小的情況下,水的面積才有可能增大
if(height[left]//向內(nèi)移動(dòng)左邊的柱子
left++;
//如果右邊的柱子更短,那么向內(nèi)移動(dòng)右邊的柱子,因?yàn)橹挥羞@樣,才有可能找到一個(gè)更高的水面
//在寬度一定變小的情況下,水的面積才有可能增大
}else{
//向內(nèi)移動(dòng)右邊的柱子
right--;
}
}
//最后返回最大的面積res即可
returnres;
}
};
3、Python 代碼
#登錄AlgoMooc官網(wǎng)獲取更多算法圖解
#https://www.algomooc.com/587.html
#作者:程序員吳師兄
#代碼有看不懂的地方一定要私聊咨詢吳師兄呀
#盛最多水的容器(LeetCode11):https://leetcode-cn.com/problems/container-with-most-water/
classSolution:
defmaxArea(self,height:List[int])->int:
#設(shè)置兩個(gè)索引,分別指向容器的兩側(cè)
#索引left指向最左邊的柱子
left=0
#索引right指向最右邊的柱子
right=len(height)-1
#設(shè)置一個(gè)變量用來保存當(dāng)下水的最大面積
res=0
#移動(dòng)left和right,直到left和right相遇為止
whileleft#水的寬度是right-left
width=right-left
#水的高度由兩根柱子最短的那根決定
h=min(height[left],height[right])
#計(jì)算此時(shí)水的面積
area=width*h
#如果此時(shí)水的面積大于了我們之前保存的那個(gè)值,我們需要更新一下
ifarea>=res:
#更新res的值為area,確保res一直都是最大的值
res=area
#接下來去觀察需要移動(dòng)哪根柱子:必定是最短的那根柱子
#如果左邊的柱子更短,那么向內(nèi)移動(dòng)左邊的柱子,因?yàn)橹挥羞@樣,才有可能找到一個(gè)更高的水面
#在寬度一定變小的情況下,水的面積才有可能增大
ifheight[left]#向內(nèi)移動(dòng)左邊的柱子
left+=1
#如果右邊的柱子更短,那么向內(nèi)移動(dòng)右邊的柱子,因?yàn)橹挥羞@樣,才有可能找到一個(gè)更高的水面
#在寬度一定變小的情況下,水的面積才有可能增大
else:
#向內(nèi)移動(dòng)右邊的柱子
right-=1
#最后返回最大的面積res即可
returnres
四、復(fù)雜度分析
時(shí)間復(fù)雜度:O(N),雙指針總計(jì)最多遍歷整個(gè)數(shù)組一次。
空間復(fù)雜度:O(1),只需要額外的常數(shù)級(jí)別的空間。
審核編輯 :李倩
-
JAVA
+關(guān)注
關(guān)注
20文章
3001瀏覽量
116434 -
容器
+關(guān)注
關(guān)注
0文章
531瀏覽量
22965 -
代碼
+關(guān)注
關(guān)注
30文章
4968瀏覽量
73970
原文標(biāo)題:雙指針,從兩頭開始內(nèi)卷,先卷了挫的那頭
文章出處:【微信號(hào):TheAlgorithm,微信公眾號(hào):算法與數(shù)據(jù)結(jié)構(gòu)】歡迎添加關(guān)注!文章轉(zhuǎn)載請(qǐng)注明出處。
發(fā)布評(píng)論請(qǐng)先 登錄
可水洗、不發(fā)霉的壓電霧化導(dǎo)水結(jié)構(gòu)(解決棉芯通病)
指針與函數(shù)詳解
函數(shù)指針介紹
指針難學(xué)的4點(diǎn)原因分析
指針的基礎(chǔ)
函數(shù)指針及指針函數(shù)的區(qū)別
函數(shù)指針的概念
如何用函數(shù)指針調(diào)用函數(shù)
C指針的妙用分享
季豐電子與盛劍科技達(dá)成戰(zhàn)略合作
雙電層超級(jí)電容器電極材料有哪些?全面解析高性能儲(chǔ)能解決方案
函數(shù)指針的六個(gè)常見應(yīng)用場(chǎng)景
盛最多水的容器:雙指針的經(jīng)典題目
評(píng)論