盛最多水的容器 图解题解

这道题真正在问什么

n 条垂线立在 x 轴上，第 i 条高 height[i]，选两条和 x 轴围成容器，求最大盛水量。面积公式是理解一切的起点：水位取决于较矮的一条——高的那条再高，水也会从矮边溢出——所以面积 = min(height[l], height[r]) × (r - l)。题目要的就是这个乘积在所有线对里的最大值。

为什么暴力枚举是 O(n²)，瓶颈在哪

枚举所有线对共约 n²/2 个，逐个算面积取最大，就是 O(n²)。慢在大量明显没前途的组合也要逐个算一遍，比如两条都很矮、又靠得近的线对。要提速，需要一个能一次排除一整批组合的判断依据——这个依据就藏在「水位由矮边决定」这条性质里。

为什么每次必须移走较矮的那端

让左右指针从最两端开始——这是宽度最大的组合。假设当前左边较矮，考虑所有「保留这条矮左边」的其他组合：右指针只能往里收，宽度必然变小；而水位仍被这条矮左边封顶，min 不可能超过它的高度。宽度变小、水位不涨，面积只会更差。也就是说，这条矮边与最远端配对的当前面积，已经是它能参与的所有组合中的最优——它的潜力被榨干了，可以放心弃掉，把指针向内移动。

这就是对撞双指针每一步的正确性依据：每轮弃掉的不是「一个位置」，而是「以该矮端为一边的全部剩余组合」，一步排除一批。n 步之后，所有可能成为最优的组合都被检查过，因此不会漏解，这也是复杂度能从平方降到线性的根本原因。

两端一样高时该移哪边

相等时随便移哪端都对。此时水位被这个相等的高度封顶，无论保留哪一端往里收，宽度都在缩、min 都不会超过当前值，两侧的剩余组合都不可能超过当前面积——而当前面积已经记录在案，之后怎么移都不会漏掉更优解。实现里写 height[l] < height[r] 时移左指针、否则移右指针即可，不需要为相等单独特判。

复杂度怎么算，容易错在哪

两个指针合计从两端走到相遇，每轮只做常数次计算，总时间 O(n)；只用 l、r、best 三个变量，空间 O(1)。最常见的错误有两个：一是用较高的一边算水位——水从矮边溢出，必须取 min，取 max 会高估面积；二是凭感觉固定移某一侧的指针——移动依据只能是「谁矮移谁」，方向错了上面的排除论证就不成立，会漏掉真正的最优组合。

Python

def maxArea(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

C++

int maxArea(vector<int>& h){
    int l = 0, r = h.size() - 1, best = 0;
    while(l < r){
        int area = min(h[l], h[r]) * (r - l);
        best = max(best, area);
        if(h[l] < h[r]) l++;
        else r--;
    }
    return best;
}

Java

public int maxArea(int[] height) {
    int l = 0, r = height.length - 1, best = 0;
    while (l < r) {
        int area = Math.min(height[l], height[r]) * (r - l);
        best = Math.max(best, area);
        if (height[l] < height[r]) l++;
        else r--;
    }
    return best;
}