11. 盛最多水的容器

给一个数组 height，height[i] 是一条竖线的高度，两条线和 x 轴围成一个容器，能装多少水由矮的那条线决定：水量 = min(左高，右高) × 两线之间的距离。题目（出处：力扣 11 盛最多水的容器）给的第一个例子是 [1, 8, 6, 2, 5, 4, 8, 3, 7]，答案是 49，取下标 1 的 8 和下标 8 的 7，宽 7，高 7。

先写最笨的办法

我一开始写的就是两层循环，把所有左右配对都算一遍，取最大的：

def max_area_bruteforce(height):
    best = 0
    for l in range(len(height)):
        for r in range(l + 1, len(height)):
            best = max(best, min(height[l], height[r]) * (r - l))
    return best

这个写法没什么可挑的，就是慢。n 条线要算 n(n-1)/2 对面积，官方例子 n=9 就要算 36 对，n=1000 就是 499500 对。答案是对的，但每次都从头算起，前面算过的信息一点没用上。我跑了一下，n=1000 的随机数据（高度 1 到 10000，种子 7）上它要枚举 499500 对，而下面这个办法只算 999 次，答案都是 9338922。

面积由矮边说了算

想快一点，得先看清面积到底由什么决定。min(左高，右高) × 宽度，宽度是两条线的距离，高度是矮的那条。也就是说，一对线能装多少水，矮边说了算，高边再高也没用。

这个观察直接给出一个办法：左指针放最左，右指针放最右，先算一次面积，然后把矮的那条往中间挪一步，再算，再挪，直到两根指针碰头。每次只挪矮边，是因为挪高边没有意义，宽度变小了，高度还是矮边那个数，面积只会更小，不可能变大。

但这样跳过很多配对，会不会把最大值漏掉？我一开始也担心这个。要想明白这一点，看固定矮边不动时会发生什么：它和任何一条内侧线配对，宽度都比现在小，高度也不会超过这条矮边，面积一定比现在小。所以这条矮边能配出的最好结果就是当前这一次，挪走它不会丢答案。每次挪走的都是一条已经没有更好配对的线，剩下的配对里最大值一定还在。走完一整趟，最大值一定算到过。

拿官方例子走一遍

数组是 [1, 8, 6, 2, 5, 4, 8, 3, 7]，下标从 0 开始：

第一步左边的 1 是全数组最矮的，挪走它没什么可惜的。第二步就撞上了答案 49。剩下的配对里左指针一直是下标 1 的 8，右端最高的 8 在下标 6，宽 5，面积 40；宽度更大的那一对右端只有 3，面积 18。所以后面超不过 40，也就超不过 49 了。整个过程只算了 8 次面积。

这里有个小地方：第四步两边都是 8，一样高，挪哪边都行。我的代码里写的是 height[l] < height[r] 时挪左，否则挪右，所以一样高时挪右。挪左也一样，因为两边相等时，无论挪哪边，丢掉的配对都不会比当前这一次更好。理由和上面一样，固定其中一边，另一边的内侧配对宽度更小、高度不超过 8。两种写法答案相同，我实测过，官方例子两种走法都是 49。

正式代码

def max_area(height):
    l, r = 0, len(height) - 1
    best = 0
    while l < r:
        # 当前这对线的面积，矮边决定高度
        area = min(height[l], height[r]) * (r - l)
        best = max(best, area)
        # 挪矮边：只有它动，面积才可能变大
        if height[l] < height[r]:
            l += 1
        else:
            r -= 1
    return best

时间复杂度 O(n)，每条线最多挪一次；额外空间 O(1)，只用了几个变量。

我拿什么验的

官方的两个例子都过了：[1, 8, 6, 2, 5, 4, 8, 3, 7] 得 49，[1, 1] 得 1。然后我写了 3000 组随机数据（先 random.seed(20261108)，长度 randint(2, 30)，高度 randint(0, 100)），把双指针的结果和暴力枚举逐个对，失配是 0 组。n=1000 那组也是同样的做法，random.seed(7)，高度 randint(1, 10000)。边界也都顺手测了：[1, 2] 和 [2, 1] 都是 1；[5, 5, 5, 5] 是 15，取两头，宽 3 高 5；递增的 [1, 2, 3, 4, 5] 是 6，取 2 和 5，宽 3 高 2；递减的 [5, 4, 3, 2, 1] 也是 6；带 0 的 [0, 0] 是 0，[0, 5, 0] 也是 0，因为矮边是 0，水量就是 0。

回头看，代码只有十来行，难处在敢不敢跳过那些没算过的配对。暴力是把所有可能都算一遍，求个安心；双指针是先想明白矮边已经没有更好的配对，才敢跳过。