Hot100-盛水最多的容器

题目链接:Hot100 - 11.盛水最多的容器

题目背景

给定一个长度为 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

解题思路

一、暴力法

易知，两根柱子left，right组成的容器能盛多少水取决于较短的柱子的高度和两根柱子之间的距离，具体的计算公式为: \[ water = min(height[left],height[right])) * (right - left) \] 暴力法的思路是找到所有可能的组合数，计算每对组合组成的容器能盛的水量，并找到最大值。时间复杂度是O（n²）。

二、双指针法

定义两个指针left、right，在开始时分别指向height数组最左的和最右的元素，当left < right时，循环以下步骤:

• 找到指向元素更小的指针
• 向内移动该指针
• 计算新的答案并与原答案比较，取更大值

方法可行性证明如下:

假设当前指向更小元素的指针是left，那么此时容器盛水的容量water1为: \[ water1 = height[left] * (right - left) \] 此时如果向内移动得到新的right，在right - left的值减小的前提，又有以下两种情况:

• height[right]的值小于height[left]。此时容器更短的柱子高度·和right - left均减小，答案一定减小。
• height[right]的值大于等于height[left]。此时容器更短的柱子高度不变，依然是height[left]，但是right - left减小，答案也一定减小。

换言之，如果left指向的元素更短，那么无论怎么移动right，结果都只可能更小。由left和[left + 1……right]组成的容器均不会是最优解。

但此时如果向内移动得到新的left，right - left的值依然减小，但是如果height[left]的值变大，由于较小值增大，计算盛水容量公式当中的其中一个因子增大。那么此时的盛水的容量warter2是有可能比warter1更大的。

也就是说，要想找到盛水量更多方法。向内移动指向元素更大的指针是完全无效的。但是向内移动`指向元素更小的指针是可以找到更优的解的。这就证明了思路的可行性。

若当前指向更小元素的指针是right也同理。

思路补充

Q：如果此时left和right指针指向的元素相等怎么办?

A：此时任意移动其中一个指针即可，理由如下:

• 如果两个指针left和right所指向的指针就是最优解，那么无论移动哪一个指针，答案都不会再更新。
• 如果再left和right中间存在更优解（i,j），那么一定有:

\[ height[i] > height[left] \]

​ 和： \[ height[j] >height[right] \] ​ 反证法:上述条件有一个不满足的话，此时更短的边只能是A = height[left] = height[right]或某个小于A的值，但无论是哪种情况，right - left的值减小，答案均减小。

​ 当满足上述两个条件后，无论先移动left或是先移动right，第一个移动指针都会停留在第一个比A更高的元素，随后再去移动另一个指针。使得（i,j）这个最优解被找到。

Q：为什么是计算right - left而不是right - left + 1?

A：right - left + 1计算的是元素个数，但实际上构成容器的底是这些元素构成的区间长度（每个区间长度为1），故一共有: \[ right - left + 1 - 1 = right -left \] 个区间，计算right-left。

具体代码

一、暴力法（会超时）

class Solution:
    def maxArea_Bruteforce(self, height: List[int]) -> int:
        #记录答案
        res = 0
        #要构成容器至少需要两根柱子，故遍历到 -1即可
        for i in range(len(height) - 1):
            for j in range(i + 1,len(height)):
                x = min(height[i],height[j]) * (j - i)
                res = max(x,res)
        return res

二、双指针法

class Solution:
    def maxArea_Twopoints(self, height: List[int]) -> int:
        #记录答案
        res = 0
        #定义指针
        left,right = 0,len(height) - 1
        #当两指针还能构成容器时循环
        while left < right:
            #计算当前两指针构成容器的盛水量
            x = min(height[left],height[right]) * (right - left)
            #当答案更大时才更新
            res = max(res,x)
            #移动指向更小元素的指针
            if height[left] < height[right]:
                left += 1
            #包括了相等的情况
            else:
                right -= 1
        return res

复杂度分析

一、暴力法

• 空间复杂度：O（1）。
• 时间复杂度：O（n²）。

二、双指针法

• 空间复杂度：O（1）。只用了常数级变量。
• 时间复杂度：O（n）。当left和right相遇时，算法结束。right和left的移动过程刚好遍历了一遍数组。