LeetCode | 盛最多水的容器

分类：双指针 / 数组

题目#

给定一个整数数组 height，数组中的每个数字表示一条竖线的高度。

任意选择两条竖线，它们和 x 轴可以组成一个容器。

求能够装下的最大水量。

示例：

1
输入：height = [1,8,6,2,5,4,8,3,7]
2
输出：49

讲解#

容器能装多少水，取决于：

1
宽度 = 两条线之间的距离
2
高度 = 两条线中较短的那条
3
面积 = 宽度 * 高度

暴力做法是枚举所有两条线的组合，计算每一对的面积。这样可以得到答案，但是有两层循环，时间复杂度是 O(n^2)。

这道题可以用双指针。先让 left 指向最左边，right 指向最右边。

当前面积是：

1
(right - left) * min(height[left], height[right])

接下来应该移动较短的那一边。

原因是：如果固定较短的那条线，只移动较高的那条线，宽度一定变小，而容器高度仍然不会超过原来的短板，所以面积不可能变大。

笔者的小巧思： 代码在这个基础上又做了一步剪枝：移动短板之后，如果新的高度还比刚才的短板更矮，就继续跳过。因为宽度已经变小，高度还更矮，这种位置也不可能得到更大的面积。

复杂度#

暴力做法：
- 时间复杂度：O(n^2)
- 空间复杂度：O(1)
双指针做法：
- 时间复杂度：O(n)
- 空间复杂度：O(1)

每个指针只会向中间移动，不会回头，所以总移动次数最多是 n 次。

代码#

源码#

1
from typing import List
2

3

4
class Solution:
5
    def maxArea(self, height: List[int]) -> int:
6
        left = 0
7
        right = len(height) - 1
8

9
        ans = 0
10
        while left < right:
11
            if height[right] < height[left]:
12
                h = height[right]
13
                area = (right - left) * h
14
                if area > ans:
15
                    ans = area
16
                right -= 1
17
                while left < right and height[right] < h:
18
                    right -= 1
19
            else:
20
                h = height[left]
21
                area = (right - left) * h
22
                if area > ans:
23
                    ans = area
24
                left += 1
25
                while left < right and height[left] < h:
26
                    left += 1
27

28
        return ans

测试#

1
from src.python._011_Container_With_Most_Water import Solution
2

3

4
sol = Solution()
5

6
assert sol.maxArea([1, 8, 6, 2, 5, 4, 8, 3, 7]) == 49
7
assert sol.maxArea([1, 1]) == 1
8
assert sol.maxArea([4, 3, 2, 1, 4]) == 16
9

10
print("PASS")

参考资料#

LeetCode 原题：https://leetcode.com/problems/container-with-most-water/
力扣官方题解：https://leetcode.cn/problems/container-with-most-water/solutions/11491/container-with-most-water-shuang-zhi-zhen-fa-yi-do/

音乐

音乐

题目#

讲解#

复杂度#

代码#

源码#

测试#

参考资料#

文章分享

评论区

音乐

文章目录