11. 盛最多水的容器

题目

给定一个长度为 $n$ 的整数数组 $height$ 。有 $n$ 条垂线，第 $i$ 条线的两个端点是 $(i,0)$ 和 $(i,height[i])$ 。找出其中的两条线，使得它们与 $x$ 轴共同构成的容器可以容纳最多的水。返回容器可以储存的最大水量。

示例

思路

1. 暴力解法

首先，我们根据例子中的图解可以得到容器中水的面积公式为：

$两条线数字的较小值\ast 两条线指针之间的距离$

• 时间复杂度：$O(n^2)$
• 空间复杂度：$O(1)$

class Solution:
    def maxArea(self, height: List[int]) -> int:
        MA = 0
        for i in range(len(height)):
            for j in range(i+1, len(height)):
                waterarea = min(height[i], height[j]) * (j-i)
                MA = max(MA, waterarea) 
        return MA
1
2
3
4
5
6
7
8

2. 双指针

$面积=两个指针指向的数字中较小值\ast 指针之间的距离$

双指针顾名思义就是左右各一个指针然后向中间移动，根据这两个指针指向的线计算面积，最不容易想到的应该就是怎么移动指针？
首先我们的面积受限于两条线中数值较短的那条线，其次左右指针开始指向第一个和最后一个，之后无论是左指针还是右指针向内移动，底边宽度都会➖1。因此直觉告诉我们，应该移动对应数字较小的那个指针，如果我们移动数字较大的那个指针，那么前者「两个指针指向的数字中较小值」不会增加，后者「指针之间的距离」会减小，那么这个乘积会减小。

证明： 假设水槽两板围成面积 $S(i,j)$，假设状态 $S(i,j)$ 下，$h[i]<h[j]$，在向内移动短板至$S(i+1,j)$ ，则相当于消去了 $S(i,j-1),S(i,j-2),...,S(i,i+1)$ 状态集合。因为这些状态：
（1）短板高度：无论 $h[j-1]h[j-2]...$比$h[j]$高还是低，相比面积 $S(i,j)$ 只能相同或更短。
（2）底边宽度：相比 $S(i,j)$ 更短；

• 时间复杂度：$O(n)$
• 空间复杂度：$O(1)$

class Solution:
    def maxArea(self, height: List[int]) -> int:
        MA = 0
        i, j = 0, len(height) - 1
        while i < j:
            waterarea = min(height[i], height[j]) * (j-i)
            MA = max(MA, waterarea) 
            if height[i] < height[j]:
                i += 1
            else:
                j -= 1
        return MA  
1
2
3
4
5
6
7
8
9
10
11
12