11. 盛最多水的容器
給定 n 個非負整數(shù) a1，a2杏死，...饲窿，an煌寇，每個數(shù)代表坐標中的一個點 (i, ai) 。在坐標內(nèi)畫 n 條垂直線逾雄，垂直線 i 的兩個端點分別為 (i, ai) 和 (i, 0)阀溶。找出其中的兩條線，使得它們與 x 軸共同構成的容器可以容納最多的水嘲驾。
示例:
圖中垂直線代表輸入數(shù)組 [1,8,6,2,5,4,8,3,7]淌哟。在此情況下，容器能夠容納水（表示為藍色部分）的最大值為 49
解題思路
- 暴力窮舉法
class Solution:
def maxArea(self, height: List[int]) -> int:
maxarea = 0
for l in range(len(height)):
if height[l]*(len(height)-1-l) < maxarea:
continue
for r in range(l+1,len(height)):
maxarea = max(maxarea, min(height[l],height[r])*(r-l))
return maxarea
#這種方法我提交一直顯示超時辽故，沒有想到更好的優(yōu)化方法，如果讀者有誰想到歡迎在評論里面指出腐碱。
- 容器面積的height受最短邊的影響誊垢，開始從最外圍開始遍歷，然后逐步從短邊到長邊遍歷症见，保存每次遍歷圍成的矩陣的面積即可
class Solution:
def maxArea(self, height: List[int]) -> int:
l = 0
r = len(height)-1
maxarea = 0
while(l<r):
maxarea = max(maxarea,min(height[l],height[r])*(r-l))
if height[l]<height[r]:
l+=1
else:
r-=1
return maxarea
