11. 盛最多水的容器

题目

给你 n 个非负整数 a_1，a_2，...，a_n，每个数代表坐标中的一个点 (i, a_i) 。在坐标内画 n 条垂直线，垂直线 i 的两个端点分别为 (i, a_i) 和 (i, 0) 。找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。
说明：你不能倾斜容器。
示例 1：

11. 盛最多水的容器 - 图1

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

示例 2：

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

示例 3：

输入：height = [4,3,2,1,4]
输出：16

示例 4：

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

提示：

  • n = height.length
  • 2 <= n <= 3 * 10^4
  • 0 <= height[i] <= 3 * 10^4

题解

分析

image.png
假设 (i*, j*) 对应的是最优解，那么 i* 左边的柱子i 必然比 i* 短，否则 (i,j*) 就是更优解。
由此可推出：i*, j* 两端以外的柱子必然比 i*, j* 中最短的还要短。

那么我们让i从最左边，j从最右边开始遍历，两个指针往中间收缩，那么怎么判断是移动i还是j呢？
我们先假设i比j短，当前面积为S=(j-i)*i ，如果移动 j，那么新的面积为
11. 盛最多水的容器 - 图3
所以新面积必然是严格变小的，因此只能移动i，也就是两根柱子中最短的一个。

那么按这个移动策略一定能**匹配**到最优解吗？
我们设最优解为 (i*, j*) ，由于两个指针往中间收缩，所以必然有一个指针能先到达最优位置，不妨设定为左指针。现在左指针到达了i*，右指针j还在j*右边，那么j的当前长度必然小于i*，否则(i*,j)就为更优解。所以右指针j为两个指针中最短的一个，因此根据策略移动右指针，这样就一定能匹配到最优解。

class Solution:
    def maxArea(self, height: List[int]) -> int:
        left,right=0,len(height)-1
        max_area=0
        while left<right:
            w=right-left
            if height[left]<height[right]:
                h=height[left]
                left+=1
            else:
                h=height[right]
                right-=1
            max_area=max(w*h,max_area)
        return max_area