盛最多水的容器
1、题目描述
给定一个长度为 n
的整数数组 height
。有 n
条垂线,第 i
条线的两个端点是 (i, 0)
和 (i, height[i])
。
找出其中的两条线,使得它们与 x
轴共同构成的容器可以容纳最多的水。
返回容器可以储存的最大水量。
说明:你不能倾斜容器。
示例 1:

1 | 输入:[1,8,6,2,5,4,8,3,7] |
示例 2:
1 | 输入:height = [1,1] |
提示:
n == height.length
2 <= n <= 105
0 <= height[i] <= 104
2、题解
2.1 双指针
题目中的示例为:
1
2[1, 8, 6, 2, 5, 4, 8, 3, 7]
^ ^在初始时,左右指针分别指向数组的左右两端,它们可以容纳的水量为 min(1,7)∗8=8。
此时我们需要移动一个指针。移动哪一个呢?直觉告诉我们,应该移动对应数字较小的那个指针(即此时的左指针)。这是因为,由于容纳的水量是由:
两个指针指向的数字中较小值∗指针之间的距离
决定的。如果我们移动数字较大的那个指针,那么前者「两个指针指向的数字中较小值」不会增加,后者「指针之间的距离」会减小,那么这个乘积会减小。因此,我们移动数字较大的那个指针是不合理的。因此,我们移动 数字较小的那个指针。所以,我们将左指针向右移动:
1
2[1, 8, 6, 2, 5, 4, 8, 3, 7]
^ ^此时可以容纳的水量为 min(8,7)∗7=49。由于右指针对应的数字较小,我们移动右指针:
1
2[1, 8, 6, 2, 5, 4, 8, 3, 7]
^ ^此时可以容纳的水量为 min(8,3)∗6=18。由于右指针对应的数字较小,我们移动右指针:
1
2[1, 8, 6, 2, 5, 4, 8, 3, 7]
^ ^此时可以容纳的水量为 min(8,8)∗5=40。两指针对应的数字相同,我们可以任意移动一个,例如左指针:
1
2[1, 8, 6, 2, 5, 4, 8, 3, 7]
^ ^此时可以容纳的水量为 min(6,8)∗4=24。由于左指针对应的数字较小,我们移动左指针,并且可以发现,在这之后左指针对应的数字总是较小,因此我们会一直移动左指针,直到两个指针重合。在这期间,对应的可以容纳的水量为:min(2,8)∗3=6,min(5,8)∗2=10,min(4,8)∗1=4。
在我们移动指针的过程中,计算到的最多可以容纳的数量为 49,即为最终的答案。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19from typing import List
class Solution(object):
def maxArea(self, height: List[int]) -> int:
l, r = 0, len(height) - 1
ans = 0
while l < r:
area = min(height[l], height[r]) * (r - l)
ans = max(ans, area)
if height[l] <= height[r]:
l += 1
else:
r -= 1
return ans
solution = Solution()
print(solution.maxArea([1, 8, 6, 2, 5, 4, 8, 3, 7]))1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16public class Solution {
public int maxArea(int[] height) {
int l = 0, r = height.length - 1;
int ans = 0;
while (l < r) {
int area = Math.min(height[l], height[r]) * (r - l);
ans = Math.max(ans, area);
if (height[l] <= height[r]) {
++l;
} else {
--r;
}
}
return ans;
}
}复杂度分析
- 时间复杂度:O(N),双指针总计最多遍历整个数组一次。
- 空间复杂度:O(1),只需要额外的常数级别的空间。