[leetcode 11] 盛最多水的容器（Python 双指针）-蒲公英云

[leetcode 11] 盛最多水的容器（Python 双指针）

蔚落 2023-02-21 06:27 77阅读 0赞

题目描述

给你 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）
链接：https://leetcode-cn.com/problems/container-with-most-water

解题思路

思路一：双指针

容纳的水量是由：两个指针指向的数字中较小值 * 指针之间的距离决定。

先从题目示例开始解释双指针算法的操作过程：
题目输入的数组为：

[1, 8, 6, 2, 5, 4, 8, 3, 7]

首先左右指针分别指向数组左右两端，此时可以容纳的水量为： min ⁡ ( 1 , 7 ) ∗ 8 = 8 \min(1,7)*8=8 min(1,7)∗8=8。
然后需要移动左右指针中对应的数较小的那个指针。
移动后变成了：

[1, 8, 6, 2, 5, 4, 8, 3, 7]

此时可以容纳的水量为 min ⁡ ( 8 , 7 ) ∗ 7 = 49 \min(8,7)*7=49 min(8,7)∗7=49。

再移动数字小的右指针：

[1, 8, 6, 2, 5, 4, 8, 3, 7]

此时可以容纳的水量为 min ⁡ ( 8 , 3 ) ∗ 6 = 18 \min(8,3)*6=18 min(8,3)∗6=18。

再移动数字小的右指针：

[1, 8, 6, 2, 5, 4, 8, 3, 7]

此时可以容纳的水量为 min ⁡ ( 8 , 8 ) ∗ 5 = 40 \min(8,8)*5=40 min(8,8)∗5=40。

两指针对应数字相同，选择其中一个。比如移动左指针：

[1, 8, 6, 2, 5, 4, 8, 3, 7]

此时可以容纳的水量为 min ⁡ ( 6 , 8 ) ∗ 4 = 24 \min(6,8)*4=24 min(6,8)∗4=24。
继续移动左指针，发现一直比右指针小所以一直移动到两指针重合。过程中对应的水量为： min ⁡ ( 2 , 8 ) ∗ 3 = 6 \min(2,8)*3=6 min(2,8)∗3=6， min ⁡ ( 5 , 8 ) ∗ 2 = 10 \min(5,8)*2=10 min(5,8)∗2=10， min ⁡ ( 4 , 8 ) ∗ 1 = 4 \min(4,8)*1=4 min(4,8)∗1=4。
所以，最多可容纳的水量为49。

正确性证明：

双指针代表可以作为容器边界的所有位置的范围。一开始双指针指向数组的左右边界表示数组中所有位置都可以作为容器的边界。然后每次将对应数字较小的指针往另一个指针的方向移动，就表示这个指针不可能当容器的边界了。最后的答案就是每次以双指针为左右边界计算出的容量中的最大值。（详细证明参见官方题解）

- 复杂度分析

时间复杂度： O ( N ) O(N) O(N)，双指针总计最多遍历整个数组一遍。
空间复杂度： O ( 1 ) O(1) O(1)，只需要额外的常数级别的空间。

代码实现

双指针:

class Solution(object):
    def maxArea(self, height):
        start, end = 0, len(height)-1
        maxwater = 0
        while start < end:
            maxwater = max(maxwater,(end - start) * min(height[start], height[end]))
            if height[start] <= height[end]:
                start = start + 1  
            else:
                end = end - 1
        return maxwater