11. 盛最多水的容器
给你 n 个非负整数
a
1
,
a
2
,
.
.
.
,
a
n
,
a_1,a_2,...,a_n,
a1,a2,...,an,每个数代表坐标中的一个点
(
i
,
a
i
)
(i, a_i)
(i,ai) 。在坐标内画 n 条垂直线,垂直线 i 的两个端点分别为
(
i
,
a
i
)
(i, a_i)
(i,ai) 和
(
i
,
0
)
(i, 0)
(i,0)。找出其中的两条线,使得它们与 x 轴共同构成的容器可以容纳最多的水。
说明: 你不能倾斜容器,且 n 的值至少为 2。
![在这里插入图片描述](https://img-blog.csdnimg.cn/20201011004416477.jpg?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzkwMTczMw==,size_16,color_FFFFFF,t_70#pic_center)
图中垂直线代表输入数组 [1,8,6,2,5,4,8,3,7]。在此情况下,容器能够容纳水(表示为蓝色部分)的最大值为 49。
Example
input |
[1,8,6,2,5,4,8,3,7] |
output |
49 |
Note
无
思路
因为容积=高度×宽度,加上数组,很容易想到从最大宽度入手,即两边入手
关键在于怎样减少宽度,以什么方式来缩短宽度。
- 对于最开始
a
1
a_1
a1和
a
n
a_n
an,假定
a
1
<
a
n
a_1<a_n
a1<an,此时
v
1
=
(
n
−
1
)
×
m
i
n
(
a
1
,
a
n
)
v_1 = (n-1)× min(a_1,a_n)
v1=(n−1)×min(a1,an)
- 如果减少宽度,让
a
1
a_1
a1向右移一位到
a
2
a_2
a2,此时
v
2
=
(
n
−
2
)
×
m
i
n
(
a
2
,
a
n
)
v_2=(n-2)× min(a_2,a_n)
v2=(n−2)×min(a2,an)
- 如果减少宽度,让
a
n
a_n
an向左移一位到
a
n
−
1
a_{n-1}
an−1,此时
v
3
=
(
n
−
2
)
×
m
i
n
(
a
1
,
a
n
−
1
)
v_3=(n-2)× min(a_1,a_{n-1})
v3=(n−2)×min(a1,an−1)
- 因为
a
1
<
a
n
a_1<a_n
a1<an,
a
2
a_2
a2和
a
n
−
1
a_{n-1}
an−1未知,那么有:
v
1
v_1
v1一定大于
v
3
v_3
v3,
v
1
v_1
v1可能小于
v
2
v_2
v2
- 所以让
a
1
,
a
n
a_1,a_n
a1,an中的
m
i
n
min
min值,移动一位减少宽度,才有可能取到更大的容积
- 以此类推,运用双指针,每次判断容积是否最大,并且让指针所指的值小的一方移动即可
代码如下
class Solution:
def maxArea(self, height: List[int]) -> int:
l, r, ans = 0, len(height)-1, -1
while l < r:
if height[l] < height[r]:
ans = max(ans, height[l] * (r-l))
l += 1
else:
ans = max(ans, height[r] * (r-l))
r -= 1
return ans