盛最多水问题：从暴力到双指针的最优解

一、问题解读

传送门：盛最多水问题

问题：给定一个整数数组 height，数组中的每个元素代表一条垂直于 x 轴的线段高度 —— 第 i 条线段的下端在 (i, 0)，上端在 (i, height[i])。我们需要挑选两条线段，和 x 轴一起围成一个 “容器”，这个容器能装的水越多越好，最终返回能装的最大水量。

举个直观例子：如果 height = [1,8,6,2,5,4,8,3,7]，最优解是选第 2 条线段（高度 8）和第 9 条线段（高度 7），容器底为 8-1=7（数组下标从 0 开始），高为 min(8,7)=7，水量就是 7×7=49，这是能装的最大水量。

示例：

关键公式：容器水量 = 底 × 高 = (右指针 - 左指针) × min(高度[右指针], 高度[左指针])（因为水不能倾斜，所以容器的 “有效高度” 由较短的线段决定，否则水会溢出）

二、暴力枚举

1. 思路分析

最直接的想法是：枚举所有可能的两条线段组合，计算每个组合的水量，最后取最大值。

• 外层循环遍历所有左线段（下标 i 从 0 到 n-2）
• 内层循环遍历所有右线段（下标 j 从 i+1 到 n-1）
• 计算每个 (i,j) 组合的水量，更新最大水量

2. 暴力代码实现

class Solution {
public:
    int maxArea(vector<int>& height) {
        int n = height.size();
        int maxWater = 0;
        // 枚举所有左线段
        for (int i = 0; i < n; ++i) {
            // 枚举所有右线段（j > i，避免重复计算）
            for (int j = i + 1; j < n; ++j) {
                int width = j - i;
                int h = min(height[i], height[j]);
                maxWater = max(maxWater, width * h);
            }
        }
        return maxWater;
    }
};

3. 暴力解法的问题

• 时间复杂度：O(n²)，n 是数组长度。当 n = 10⁴ 时，运算次数达到 10⁸ 级别，会直接超时
• 空间复杂度：O(1)，只用到几个临时变量

暴力解法的核心问题是 “无差别枚举”—— 很多组合的水量明显很小，却还要重复计算，效率极低。我们需要找到一种 “聪明的搜索方式”，减少不必要的计算。

三、优化核心：找到 “剪枝” 的逻辑

要优化，先思考：容器的水量由什么决定？

是两个因素：底的长度（右指针 - 左指针）和 有效高度（两条线段的最小值）。

初始时，我们可以用 “最大的底”—— 左指针在最左（0），右指针在最右（n-1）。此时底最长，但有效高度由较短的线段决定。接下来要移动指针缩小底的长度，怎么移动才能让水量 “有可能变大”？

关键

• 如果移动 较长的线段：新的有效高度要么不变（新线段比原来的短线段长），要么变小（新线段比原来的短线段还短）。而底的长度一定变小，所以水量必然变小。
• 如果移动 较短的线段：新的有效高度有可能变大（新线段比原来的短线段长），虽然底的长度变小，但有效高度的增加可能抵消底的减少，从而让水量变大。

所以，每次移动较短的线段指针，是唯一有可能找到更大水量的选择！

四、双指针法

基于上面的结论，我们可以设计出双指针算法，时间复杂度优化到 O(n)。

class Solution {
public:
    int maxArea(vector<int>& height) {
        int l = 0; // 左指针初始在最左
        int r = height.size() - 1; // 右指针初始在最右
        int res = 0; // 存储最大水量
        int total; // 临时存储当前水量
        while (l < r) { // 循环条件：左右指针不重合（重合时底为0，水量为0）
            // 计算当前容器的水量
            total = (r - l) * min(height[r], height[l]);
            // 更新最大水量
            res = max(res, total);
            // 移动较短的线段指针
            if (height[l] < height[r]) {
                l++; // 左线段短，左指针右移
            } else {
                r--; // 右线段短（或相等），右指针左移
            }
        }
        return res;
    }
};

复杂度分析

• 时间复杂度：O(n)。左、右指针最多各移动 n 次，循环执行次数不超过 n 次，比暴力解法快一个量级。
• 空间复杂度：O(1)。只使用了 4 个临时变量，没有额外占用空间。

五、示例模拟：直观感受算法执行过程

用示例 height = [1,8,6,2,5,4,8,3,7] 模拟双指针移动过程，让你看清每一步的计算：

左指针 l	右指针 r	height[l]	height[r]	底（r-l）	有效高度 min (...)	当前水量	最大水量 res	移动方向（原因）
0	8	1	7	8	1	8	8	l++（1<7，移左）
1	8	8	7	7	7	49	49	r--（7<8，移右）
1	7	8	3	6	3	18	49	r--（3<8，移右）
1	6	8	8	5	8	40	49	任意移（相等，这里移 r--）
1	5	8	4	4	4	16	49	r--（4<8，移右）
1	4	8	5	3	5	15	49	r--（5<8，移右）
1	3	8	2	2	2	4	49	r--（2<8，移右）
1	2	8	6	1	6	6	49	r--（6<8，移右）
1	1	-	-	0	-	-

最终最大水量为 49，和预期一致。

这个思路不仅适用于本题，还能迁移到很多数组双指针问题（比如两数之和、接雨水等）。核心是：找到问题的关键影响因素，制定剪枝策略，减少不必要的计算。