1. 题目

11. 盛最多水的容器

题目描述

给定长度为 n 的整数数组 height，每个元素代表坐标轴上竖直柱子高度。

任选两根柱子，以两根柱子的横坐标距离为宽、较小柱子高度为高，构成容器，求容器可装水的最大面积。

示例

输入：height = [1,8,6,2,5,4,8,3,7]

输出：49

解释：左柱 8（下标 1）、右柱 7（下标 8），宽 7，高 7，面积 7*7=49

约束

• (n = height.length)

• (2 < n < 10^5)

• (0 < height[i] < 10^4)

2. 两种解题思路

思路 1：暴力双重循环（你的代码）

枚举所有左右柱子组合，计算面积并记录最大值。

• 时间：(O(n^2))，数组长度上万直接超时，无法通过大数据用例；

• 仅适合理解题意，面试不能作为正解。

思路 2：双指针（最优，(O(n))）

1. 左指针 l 在最左，右指针 r 在最右，初始宽度最大；

2. 计算当前面积，更新全局最大值；

3. 移动规则：

   移动高度更小的一侧指针

   • 若 height[l] < height[r]：l 右移，尝试找更高左柱；

   • 否则：r 左移，尝试找更高右柱；

4. 两指针相遇停止。

   原理：短板决定高度，保留长板，移动短板才有可能得到更大面积。

3. 暴力代码分析

class Solution {
public:
    int maxArea(vector<int>& height) {
        int res = -1;
        for(int i = 0;i<height.size()-1;i++){
            for(int j = i+1;j<height.size();j++){
                res = max(res,min(height[i],height[j])*(j-i));
            }
        }
        return res;
    }
};

优点

逻辑直白，完全贴合题意，无理解门槛。

致命缺陷

1. 时间复杂度 (O(n^2))，(n=10^5) 时运算量上亿，超时；

2. 初始值 res=-1 无问题（面积必然≥0），但规范初始化为 0 更直观；

3. 重复大量无意义组合计算，存在大量冗余。

4. 标准双指针最优代码

#include <vector>
#include <algorithm>
using namespace std;
class Solution {
public:
    int maxArea(vector<int>& height) {
        int l = 0, r = height.size() - 1;
        int maxS = 0;
        while (l < r) {
            int h = min(height[l], height[r]);
            int w = r - l;
            maxS = max(maxS, h * w);
            if (height[l] < height[r]) {
                l++;
            } else {
                r--;
            }
        }
        return maxS;
    }
};

5. 总结

1. 暴力双循环仅用于理解题目，大数据必超时，面试必须写双指针；

2. 双指针核心：移动短边，保留长边；

3. 面积公式：min(左高,右高) * 下标间距；

4. 循环终止条件 l < r，两柱子不能是同一根。

6. 拓展对比

复杂度对比

• 暴力枚举：(O(n^2)) 时间，(O(1)) 空间（超时）

• 双指针：(O(n)) 时间，(O(1)) 空间（最优）

易错点复盘

1. 双指针错误移动长边，只会不断缩小宽度且高度不变，面积只会更小；

2. 循环条件写成 l <= r，同一根柱子无宽度，不影响结果但多余；

3. 忘记取两个高度最小值，直接用乘积导致答案偏大。