LeetCode(Python实现)—盛最多水的容器
再次记录 LeetCode 刷题之路!!
题目描述
给出一个非负整数数组 a1,a2,a3,…… an
,每个整数标识一个竖立在坐标轴x
位置的一堵高度为ai
的墙,选择两堵墙,和 x
轴构成的容器可以容纳最多的水。
输入:[1,8,6,2,5,4,8,3,7]
输出:49
解题思路
这一题是指针对撞的思路。首尾分别 2 个指针,每次移动以后都分别判断长宽的乘积是否最大。设两指针 left , right ,指向的水槽板高度分别为
h
[
l
e
f
t
]
,
h
[
r
i
g
h
t
]
h[left], h[right]
h[left],h[right],此状态下水槽面积为
S
(
l
e
f
t
,
r
i
g
h
t
)
S(left, right)
S(left,right) 。由于可容纳水的高度由两板中的短板决定。
因此面积的计算公式为:
S
(
l
e
f
t
,
r
i
g
h
t
)
=
m
i
n
(
h
[
l
e
f
t
]
,
h
[
r
i
g
h
t
]
)
×
(
r
i
g
h
t
−
l
e
f
t
)
S(left,right)=min(h[left],h[right])×(right−left)
S(left,right)=min(h[left],h[right])×(right−left)
class Solution:
def maxArea(self, height: list[int]) -> int:
left, right = 0, len(height)-1
res = 0
while left < right:
if height[left] < height[right]:
res = max(res, min(height[left], height[right]) * (right - left))
left += 1
else:
res = max(res, min(height[left], height[right]) * (right - left))
right -= 1
return res
更多推荐
所有评论(0)