LeetCode 11. 盛最多水的容器

◎

本节目标

从两端相向移动较短边，以线性时间寻找最大面积。

这题是双指针解题框架中相向收缩的证明题：移动规则来自当前短板，而非直觉。

查看原题

题意与约束

选择两条竖线组成容器，容量为两端较低高度乘以两条线的横向距离，求最大容量。

推导与不变量

最直接的办法是枚举所有边界对并计算面积，时间复杂度为 O(n²)。瓶颈在于重复比较了大量不可能优于当前答案的组合；若能一次排除一组这样的组合，就不必逐对检查。

因此从最宽的两端开始相向收缩。假设左边更短，任何仍保留左边界的组合宽度都会更小，最低高度也不会超过当前左边高度，因此不可能超过当前面积；左边界可以安全丢弃。右边更短时同理。[left, right] 始终保留尚未被证明不可能更优的边界。

代码实现

每轮先计算当前面积，再移动较短的一侧；两端相等时移动任意一侧均正确，源码选择移动右侧。

C++

C++17

#include <algorithm>
#include <vector>

using namespace std;

class Solution {
public:
    int maxArea(vector<int>& height) {
        int left = 0;
        int right = static_cast<int>(height.size()) - 1;
        int best = 0;

        while (left < right) {
            best = max(best, min(height[left], height[right]) * (right - left));
            if (height[left] < height[right]) {
                left++;
            } else {
                right--;
            }
        }
        return best;
    }
};

Python

Python 3

class Solution:
    def maxArea(self, height: list[int]) -> int:
        left = 0
        right = len(height) - 1
        best = 0

        while left < right:
            best = max(best, min(height[left], height[right]) * (right - left))
            if height[left] < height[right]:
                left += 1
            else:
                right -= 1
        return best

复杂度分析

• 时间复杂度：O(n)，每个边界至多移动一次。
• 空间复杂度：O(1)。

易错点

• 移动较高边：短板和宽度都没有改善的保证，无法安全排除候选。
• 只在移动后计算面积，漏掉初始的最宽候选。

模式迁移

相向指针的核心是用单调性安全地删除候选。排序后的两数之和、三数之和也用“和偏大或偏小”决定移动方向。