LeetCode_11_中等_盛最多水的容器

1. 题目

给定一个长度为 $n$ 的整数数组 $height$ 。有 $n$ 条垂线，第 $i$ 条线的两个端点是 $(i,0)$ 和 $(i,height[i])$ 。

找出其中的两条线，使得它们与 $x$ 轴共同构成的容器可以容纳最多的水。

返回容器可以储存的最大水量。

说明：你不能倾斜容器。

示例 1：

输入：[1,8,6,2,5,4,8,3,7]
输出：49
解释：图中垂直线代表输入数组 [1,8,6,2,5,4,8,3,7]。在此情况下，容器能够容纳水（表示为蓝色部分）的最大值为 49。

示例 2：

输入：height = [1,1]
输出：1

提示：

• $n==height.length$
• $2<=n<=10^5$
• $0<=height[i]<=10^4$

2. 思路及代码实现（Python）

2.1 双指针

这里有一个很直接的方式，就是遍历所有的容器边界组合，一个个对比找到装水最多的，但是这样的算法复杂度为 $O(n^2)$，那是否有办法缩减掉一些组合呢？使得我们并不需要遍历所有的组合也能找到容量最大的容器。

这个方法就是双指针，在列表的左右两端生成指针，不断地把指针向中间靠拢，能够覆盖所有地容器边界情况，但是每一次移动指针，都会缩减一部分边界组合，这里就有一个问题，到底需要移动哪个指针？假设有两个指针在列表的 $i,j$ 位置，其中，$height[i]<height[j]$，不论我们移动哪一边的指针，容器的长都会减小，且容器的高取决于最矮的边界，因此，对于左指针（较矮）而言，不会有包含左指针的组合且容量还大于当前组合的情况了，因此左指针可以移动。

例如：[3，>2，6，8，3，2，4<]，假设左指针在2，右指针在4，此时的容器容量为 $5\times 2=10$，显然，不论我们如何移动右指针，只要左指针还是2的位置，那右指针的值可能比4高，或者比4低甚至比2低，但新容器的长都会小于5，且高不会高于2（取边界的较小值），因此固定左指针2之后的容器容量不会再高于10，此时可以舍弃左指针的位置，向右移动。

依次类推，左右指针不断把较小值向中间推移，最终得到的较大容量即为总体最大的容量。此时，由于指针只移动了 $n$ 次，因此算法时间复杂度为 $O(n)$，而移动指针的过程只记录指针位置和当前最大值，空间复杂度为$O(1)$。

class Solution:
    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

执行用时：169 ms
消耗内存：26.77 MB

参考来源：力扣官方题解