✨ 把代码写进星轨，用逻辑丈量宇宙。

导航	链接
个人主页	🏠 星轨初途
基础语言专栏	💻 C语言、📚 数据结构
刷题实战专栏	🚀 算法及编程题分享、📝 力扣每日刷题分享

🌊 今天继续开启 LeetCode 刷题之旅(*￣︶￣)！这次我们要寻找一个“最能装水”的容器。看起来需要比较很多组合，但双指针一出场，一次遍历就能轻松拿下！

盛最多水的容器

---

题目思路

数组中的每个元素表示一条竖线的高度，需要选择两条竖线和 x 轴组成一个容器，使容器能够盛放最多的水。

假设选择的两条竖线下标分别为 l 和 r，那么：

容器宽度 = r - l
容器高度 = min(height[l], height[r])

因此，容器面积为：

(r - l) * min(height[l], height[r])

如果暴力枚举所有竖线组合，时间复杂度为 O(n²)，所以这里使用双指针进行优化。

---

方法：双指针

容器能够装多少水，由两条边中较短的一条决定。

假设左右两条边的位置分别为 l 和 r，那么：

容器的最低水位 = min(height[l], height[r])
容器的宽度 = r - l

所以面积为：

min(height[l], height[r]) * (r - l)

我们可以把这道题理解为：

依次考虑每一条竖线作为容器最低边时，它所能得到的最大面积，最后从这些面积中取最大值。

双指针开始时：

l 指向最左边
r 指向最右边

此时两条边之间的距离最远。

假设左边较短：

height[l] <= height[r]

那么当前容器的最低水位就是 height[l]。

此时右边已经是当前范围内距离左边最远的位置，所以当前面积就是在当前有效范围内，以左边这条线作为最低边时所能得到的最大面积。

如果继续保留左边，只移动右边：

• 容器宽度会变小；
• 最低水位仍然不会超过 height[l]。

因此面积不可能变得更大，左边这条线已经没有继续保留的必要，可以让：

l++;

同理，如果右边较短，就说明已经计算出了以右边作为最低边时能够得到的最大面积，因此让：

r--;

不断重复这个过程，每次处理并舍弃较短的一边，最终取所有计算结果中的最大值。

复杂度分析

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

两个指针最多各移动 n 次，不需要使用额外数组。

代码

class Solution {
public:
    int maxArea(vector<int>& height) {
        // 左右双指针
        int l=0,r=height.size()-1;

        // 记录最大面积
        int max_num=0;

        while(l<r)
        {
            // 容器高度由较短的一边决定
            int x = min(height[l],height[r]);

            // 更新最大面积
            max_num = max(max_num,(r-l)*x);

            // 移动较短的一侧
            if(x==height[l])l++;
            else r--;
        }

        return max_num;
    }
};

当左右两边高度相等时，代码会移动左指针。此时移动任意一边都可以，因为当前容器高度相同，只有缩小范围继续寻找更高的竖线，才可能得到更大的面积。

---

为什么移动较短的一边

假设当前：

height[l] < height[r]

那么容器的最低水位由 height[l] 决定。

当前 r 已经处在最远的位置，因此当前面积为：

height[l] * (r - l)

如果移动较高的右边，左边仍然是最低边，但宽度却变小了，所以面积一定不会超过当前面积。

因此，当前已经得到了以左边这条线作为最低边时，在当前范围内能够获得的最大面积，可以舍弃左边，继续寻找新的最低边。

代码中的：

if(x==height[l])l++;
else r--;

表达的就是：

哪一边决定了当前容器的最低水位，就处理并舍弃哪一边；另一边暂时保留，继续尝试组成更大的容器。

最后将每次得到的面积进行比较，就能得到整个数组中可以盛水的最大面积。

---

总结

方法	核心思路	时间复杂度	空间复杂度
双指针	每次移动较短的一侧寻找更优答案	O(n)	O(1)

这道题最关键的地方，就是理解为什么要移动较短的那条竖线。

双指针让我们不需要枚举所有组合，只需要从两端不断缩小范围，就能在线性时间内找到最大面积。

🎉 今天的“装水挑战”成功完成！双指针虽然代码不长，但背后的贪心思想非常值得掌握。每天解决一道题，让我们的算法星轨继续向前延伸，下一题再见！

ヾ(◍°∇°◍)ﾉﾞ