Leetcode 11.乘最多水的容器(字节,快手面试题)
题目链接:11. 盛最多水的容器 - 力扣(LeetCode)
题目描述:
给定一个长度为 n
的整数数组 height
。有 n
条垂线,第 i
条线的两个端点是 (i, 0)
和 (i, height[i])
。找出其中的两条线,使得它们与 x
轴共同构成的容器可以容纳最多的水。返回容器可以储存的最大水量。
说明:你不能倾斜容器。
示例 1:
输入:[1,8,6,2,5,4,8,3,7]
输出:49
解释:图中垂直线代表输入数组 [1,8,6,2,5,4,8,3,7]。在此情况下,容器能够容纳水(表示为蓝色部分)的最大值为 49。
解题思路:双指针
可容纳的最大体积由最小的那个值决定
1.定义左右两个指针分别代表容器最左和最右板
2.首先判断所给数组的长度,若<=1,则直接返回0
3.若==2,说明只有两个元素,宽为1,可容纳体积为,高为最小元素
4.初始化体积为左右指针的较小值为高,宽为左右指针的差值
5.每次判断左右指针指向值的大小,总是为了保证容积的最大值,所以移动指针值小的那一个
代码:
class Solution:
def maxArea(self, height: List[int]) -> int:
left = 0
n = len(height)
right = n - 1
if n <= 1:
return 0
if n == 2 :
return min(height[0],height[1])
max_v = min(height[left],height[right]) * ( n-1 )
while left < right :
if height[left] < height[right]:
left += 1
v = min(height[left],height[right]) * (right - left)
max_v = max(v,max_v)
elif height[right] <= height[left]:
right -= 1
v = min(height[left],height[right]) * (right - left)
max_v = max(v,max_v)
return max_v