大家好，我是吳師兄，

今天的題目來源于 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í)別的空間。