Posted on 2022-10-31 18:30
Uriel 阅读(49)
评论(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