題目
描述
給你 n 個非負整數 a1，a2，...，an，每個數代表坐標中的一個點 (i, ai) ，在坐標內畫 n 條垂直線，垂直線 i 的兩個端點分別為 (i, ai) 和 (i, 0) ，找出其中的兩條線，使得它們與 x 軸共同構成的容器可以容納最多的水，
說明：你不能傾斜容器，
示例1
輸入：[1,8,6,2,5,4,8,3,7]
輸出：49
解釋：圖中垂直線代表輸入陣列 [1,8,6,2,5,4,8,3,7]，在此情況下，容器能夠容納水（表示為藍色部分）的最大值為 49，示例2
輸入：height = [1,1]
輸出：1示例3
輸入：height = [4,3,2,1,4]
輸出：16示例4
輸入：height = [1,2,1]
輸出：2提示
（1）n == height.length
（2）2 <= n <= 105
（3）0 <= height[i] <= 104
解題思路
（1）水的面積由選中的左右連根垂直線中的最小那根決定
（2）由外到內不斷剔除最小的那根垂直小，記錄當前面積
（3）如果當前面積比前一次計算的面積大，則將當前面積替換掉上一次的面積
（4）直到不能剔除垂直線結束
（5）輸出記錄下來的最大面積
代碼
class Solution:
def maxArea(self, height: List[int]) -> int:
l, r = 0, len(height) - 1
ans = 0
while l < r:
area = min(height[l], height[r]) * (r - l)
ans = max(ans, area)
if height[l] <= height[r]:
l += 1
else:
r -= 1
return ansReference
題庫 - 力扣 (LeetCode) 全球極客摯愛的技術成長平臺
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/301046.html
標籤：python
上一篇：解決python安裝依賴包出現 Microsoft Visual C++ 14.0 or greater is required問題