Posted on 2022-10-31 18:30
Uriel 閱讀(77)
評論(0) 編輯 收藏 引用 所屬分類:
貪心 、
閑來無事重切Leet Code
給一列數組，代表1-len(matrix)每個位置的桶高，問設立左右兩個邊界之后最多能盛多少水
貪心，左右兩個游標分別向中間移動，每次移動桶高小的游標，更新最大水量
1 #11
2 #Runtime: 1703 ms
3 #Memory Usage: 23.9 MB
4
5 class Solution(object):
6 def maxArea(self, height):
7 """
8 :type height: List[int]
9 :rtype: int
10 """
11 p1 = 1
12 p2 = len(height)
13 ans = min(height[0], height[-1]) * (p2 - p1)
14 while p1 < p2 - 1:
15 if height[p1 - 1] < height[p2 - 1]:
16 p1 += 1
17 else:
18 p2 -= 1
19 ans = max(ans, min(height[p1 - 1], height[p2 - 1]) * (p2 - p1))
20 return ans