1 題目描述

2 解題思路

雙指針

算法流程： 設(shè)置雙指針 i,j 分別位于容器壁兩端，根據(jù)規(guī)則移動(dòng)指針（規(guī)則后文會(huì)提及），并且更新面積最大值 res，直到 i >?j 時(shí)返回 res。

?

指針移動(dòng)規(guī)則與證明： 每次選定圍成水槽兩板高度 h[i],h[j]中的短板，向中間收窄 1 格。

?

以下證明：

設(shè)每一狀態(tài)下水槽面積為 S(i, j)(0<=i<j<n)，由于水槽的實(shí)際高度由兩板中的短板決定，則可得面積公式 S(i, j) = min(h[i], h[j]) × (j - i)。

在每一個(gè)狀態(tài)下，無(wú)論長(zhǎng)板或短板收窄 1 格，都會(huì)導(dǎo)致水槽 底邊寬度 -1：

若向內(nèi)移動(dòng)短板，水槽的短板 min(h[i], h[j])可能變大，因此水槽面積 S(i, j) 可能增大。

若向內(nèi)移動(dòng)長(zhǎng)板，水槽的短板 min(h[i], h[j])不變或變小，下個(gè)水槽的面積一定小于當(dāng)前水槽面積（j-i）變小了。

因此，向內(nèi)收窄短板可以獲取面積最大值。

?

從剪枝的角度理解算法：

若不指定移動(dòng)規(guī)則，所有移動(dòng)出現(xiàn)的 S(i, j) 的狀態(tài)數(shù)為 C(n, 2)，即暴力枚舉出所有狀態(tài)。

在狀態(tài) S(i, j)下向內(nèi)移動(dòng)短板至 S(i + 1, j)（假設(shè) h[i] < h[j] ），則相當(dāng)于消去了 {S(i, j - 1), S(i, j - 2), ... , S(i, i + 1)} 狀態(tài)集合。而所有消去狀態(tài)的面積一定 <= S(i, j)：

短板高度：相比 S(i, j) 相同或更短（<= h[i]）；

底邊寬度：相比 S(i, j) 更短。

因此所有消去的狀態(tài)的面積都 < S(i, j)。

換句話說(shuō)，我們每次向內(nèi)移動(dòng)短板，所有的消去狀態(tài)都不會(huì)導(dǎo)致丟失面積最大值 。

?

復(fù)雜度分析：

時(shí)間復(fù)雜度 O(N)，雙指針遍歷一次底邊寬度 N 。

空間復(fù)雜度 O(1)，指針使用常數(shù)額外空間。

class Solution:def maxArea(self, height: List[int]) -> int:first=0last=len(height)-1 #起始和終止位置的指針max_l=0 #當(dāng)前最大蓄水量while(first<last):tmp=min(height[first],height[last])*(last-first)max_l=max(tmp,max_l)if(height[first]<=height[last]):first+=1else:last-=1return(max_l)

?

總結(jié)

以上是生活随笔為你收集整理的文巾解题 11. 盛最多水的容器的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。