大家好，我是吳師兄，

今天的題目來源于 LeetCode 第 11 號問題：盛最多水的容器，難度為「中等」，屬于雙指針的經(jīng)典題目。

一、題目描述

給你 n 個非負(fù)整數(shù) a1，a2，...，an，每個數(shù)代表坐標(biāo)中的一個點 (i, ai) 。在坐標(biāo)內(nèi)畫 n 條垂直線，垂直線 i 的兩個端點分別為 (i, ai) 和 (i, 0) 。

找出其中的兩條線，使得它們與 x 軸共同構(gòu)成的容器可以容納最多的水。

二、題目解析

一開始，我們先去考慮相距最遠(yuǎn)的兩個柱子所能容納水的面積。

接下來去思考，我們?nèi)ヒ苿幽母訒雍线m?

這里我們需要注意一點：無論移動哪根柱子，柱子之間的寬度都是變小的。

移動右邊那根更高的柱子？

由于水面高度是由最短的柱子決定的，所以移動右邊那根更高的柱子的時候，水面高度一定是不會增加，甚至有可能遇到更短的柱子而變小，而寬度有一定再減少，所以水的面積也一定減少。

移動左邊那根更短的柱子？

這時候，水的高度是不確定的，那么面積也是不確定的，有可能比之前更大，也有可能更小或者相等。

所以，我們可以得出一個結(jié)論：移動兩根柱子之間更短的那根柱子，才有可能在寬度一定變小的情況下，找到一個更高的水面，從而使得面積有可能更大。

那接下來這道題目的解法也就有了：

1、設(shè)置兩個索引，分別指向容器的兩側(cè)，即索引left指向最左邊的柱子，索引right指向最右邊的柱子。

2、記錄下此時的水的面積，可以定義為 res

3、觀察需要向內(nèi)移動哪根柱子

• 1）如果移動較高的柱子，由于水的寬度在變小，而水的高度一定不會增加，所以最終水的面積不會超過之前記錄的水的面積 res
• 2）所以，只能移動較短的柱子，然后計算此時水的面積，再與之前記錄的水的面積 res 進行比較，保存那個更大的值

4、再去判斷應(yīng)該向內(nèi)移動哪根柱子

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è)置兩個索引，分別指向容器的兩側(cè)

//索引left指向最左邊的柱子
intleft=0;

//索引right指向最右邊的柱子
intright=height.length-1;

//設(shè)置一個變量用來保存當(dāng)下水的最大面積
intres=0;

//移動left和right，直到left和right相遇為止
while(left//水的寬度是right-left
intwidth=right-left;

//水的高度由兩根柱子最短的那根決定
inth=Math.min(height[left],height[right]);

//計算此時水的面積
intarea=width*h;

//如果此時水的面積大于了我們之前保存的那個值，我們需要更新一下
if(area>=res){
//更新res的值為area，確保res一直都是最大的值
res=area;
}

//接下來去觀察需要移動哪根柱子：必定是最短的那根柱子

//如果左邊的柱子更短，那么向內(nèi)移動左邊的柱子，因為只有這樣，才有可能找到一個更高的水面
//在寬度一定變小的情況下，水的面積才有可能增大
if(height[left]//向內(nèi)移動左邊的柱子
left++;

//如果右邊的柱子更短，那么向內(nèi)移動右邊的柱子，因為只有這樣，才有可能找到一個更高的水面
//在寬度一定變小的情況下，水的面積才有可能增大
}else{
//向內(nèi)移動右邊的柱子
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è)置兩個索引，分別指向容器的兩側(cè)

//索引left指向最左邊的柱子
intleft=0;

//索引right指向最右邊的柱子
intright=height.size()-1;

//設(shè)置一個變量用來保存當(dāng)下水的最大面積
intres=0;

//移動left和right，直到left和right相遇為止
while(left//水的寬度是right-left
intwidth=right-left;

//水的高度由兩根柱子最短的那根決定
inth=min(height[left],height[right]);

//計算此時水的面積
intarea=width*h;

//如果此時水的面積大于了我們之前保存的那個值，我們需要更新一下
if(area>=res){
//更新res的值為area，確保res一直都是最大的值
res=area;
}

//接下來去觀察需要移動哪根柱子：必定是最短的那根柱子

//如果左邊的柱子更短，那么向內(nèi)移動左邊的柱子，因為只有這樣，才有可能找到一個更高的水面
//在寬度一定變小的情況下，水的面積才有可能增大
if(height[left]//向內(nèi)移動左邊的柱子
left++;

//如果右邊的柱子更短，那么向內(nèi)移動右邊的柱子，因為只有這樣，才有可能找到一個更高的水面
//在寬度一定變小的情況下，水的面積才有可能增大
}else{
//向內(nèi)移動右邊的柱子
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è)置兩個索引，分別指向容器的兩側(cè)

#索引left指向最左邊的柱子
left=0

#索引right指向最右邊的柱子
right=len(height)-1

#設(shè)置一個變量用來保存當(dāng)下水的最大面積
res=0

#移動left和right，直到left和right相遇為止
whileleft#水的寬度是right-left
width=right-left

#水的高度由兩根柱子最短的那根決定
h=min(height[left],height[right])

#計算此時水的面積
area=width*h

#如果此時水的面積大于了我們之前保存的那個值，我們需要更新一下
ifarea>=res:
#更新res的值為area，確保res一直都是最大的值
res=area

#接下來去觀察需要移動哪根柱子：必定是最短的那根柱子

#如果左邊的柱子更短，那么向內(nèi)移動左邊的柱子，因為只有這樣，才有可能找到一個更高的水面
#在寬度一定變小的情況下，水的面積才有可能增大
ifheight[left]#向內(nèi)移動左邊的柱子
left+=1

#如果右邊的柱子更短，那么向內(nèi)移動右邊的柱子，因為只有這樣，才有可能找到一個更高的水面
#在寬度一定變小的情況下，水的面積才有可能增大
else:
#向內(nèi)移動右邊的柱子
right-=1

#最后返回最大的面積res即可
returnres

四、復(fù)雜度分析

時間復(fù)雜度：O(N)，雙指針總計最多遍歷整個數(shù)組一次。

空間復(fù)雜度：O(1)，只需要額外的常數(shù)級別的空間。