难度:Medium.
给定 n 个非负整数 a1,a2,...,an,每个数代表坐标中的一个点 (i, ai) 。在坐标内画 n 条垂直线,垂直线 i 的两个端点分别为 (i, ai) 和 (i, 0)。找出其中的两条线,使得它们与 x 轴共同构成的容器可以容纳最多的水。
说明:你不能倾斜容器,且 n 的值至少为 2。
图中垂直线代表输入数组 [1,8,6,2,5,4,8,3,7]。在此情况下,容器能够容纳水(表示为蓝色部分)的最大值为 49。
示例:
输入: [1,8,6,2,5,4,8,3,7]
输出: 49
解析:
这里的相关标签是:数组,双指针
.
我们也见过一些双指针的题了,包括[leetcode] 19. 删除链表的倒数第N个节点, [leetcode] 3.无重复字符的最长字串,特点都是用两个指针,圈出一片区域,保证这篇区域最大,或者最长,或者不变。
这道题也是这样,是用两个指针,圈出一片区域,保证这篇区域最大。
很自然应对这种找最大的题,会有2种解法。
- 暴力解;
- 取巧解。
暴力解很好理解,将list里任意2数的所有组合,取最大。
时间复杂度:.取巧解就是双指针的方法。
水槽面积 =
最大的长,就左指针L
=0,右指针R
=n-1。
最大的宽呢,不确定。
指针移动规则:
每次选定围成水槽两板高度 , 中的短板,向中间收窄 1 格。
证明:
假设 , 面积左侧向内收缩至。那么就等于消去了面积,注意这里:
因为:
- :只会小于或等于;
- :只会小于。
因此,所有消去的面积都。因此消去的状态不会动摇最大面积。
代码:
def maxArea(height):
L = 0
R = len(height)-1
area_max = min(height[L], height[R])*(R-L)
while L < R:
if height[L] < height[R]:
L += 1
else:
R -= 1
area_max = max(area_max, min(height[L], height[R])*(R-L))
return area_max