11. 盛最多水的容器#

生活中的算法#

你有没有遇到过这样的场景：家里要举办派对，需要准备一个大容器来调制果汁。面前有很多不同高度的挡板，你需要选择两个，插到容器里，这样就能盛放饮料了。挡板的高度不同，间距也可以调整，你要怎么选择才能盛放最多的饮料呢？

这就是我们今天要讲的”盛最多水的容器”问题。本质上，我们要在一排不同高度的”墙”中选择两堵墙，使它们之间能容纳最多的水。

问题描述#

题目目标#

LeetCode第11题”盛最多水的容器”是这样描述的：给定一个长度为n的整数数组height，有n条垂线，第i条线的两个端点是(i, 0)和(i, height[i])。找出其中的两条线，使得它们与x轴共同构成的容器可以容纳最多的水。

示例 1#

输入： height = [1,8,6,2,5,4,8,3,7] 输出： 49 说明： 把输入和输出放在一起看，会更容易直接抓住题目要求的变化。

最直观的解法：暴力枚举法#

最容易想到的方法就是：尝试所有可能的容器组合，找出能盛水最多的那个。就像我们实际准备容器时，可能会挨个试一试每种组合。

具体步骤是这样的：

使用两层循环，遍历所有可能的左右边界组合
对每个组合，计算其能容纳的水量
更新最大水量

让我们用一个小例子来模拟这个过程：

height = [1,8,6,2]

尝试所有组合：
(0,1): min(1,8) * 1 = 1
(0,2): min(1,6) * 2 = 2
(0,3): min(1,2) * 3 = 3
(1,2): min(8,6) * 1 = 6
(1,3): min(8,2) * 2 = 4
(2,3): min(6,2) * 1 = 2

最大容积 = 6

plaintext

这种思路可以用Java代码这样实现：

public int maxArea(int[] height) {
    // maxVolume 记录遍历过程中找到的最大容积
    int maxVolume = 0;

    // i 作为容器左边界，逐个尝试
    for (int i = 0; i < height.length; i++) {
        // j 作为容器右边界，始终在 i 的右侧
        for (int j = i + 1; j < height.length; j++) {
            // 计算当前组合的容积
            // 容积 = 两边较矮一边的高度 * 两边的距离
            // volume 表示当前 i、j 这对边界形成的容积
            int volume = Math.min(height[i], height[j]) * (j - i);
            // 用当前容积尝试更新历史最大值
            maxVolume = Math.max(maxVolume, volume);
        }
    }

    // 返回最终最大容积
    return maxVolume;
}

java

优化解法：双指针法#

仔细思考，我们其实不需要尝试所有组合。关键是理解：容器的容积取决于两个因素：

两边中较短的那条边（决定了水的高度）
两边的距离（决定了水的宽度）

如果我们从最宽的容器开始，逐渐向内收缩，每次都移动较短的那条边，就一定不会错过最大容积。

双指针法的原理#

为什么这样做是对的？假设我们有两个指针left和right：

容积由较短的边决定
如果移动较长的边，宽度减小，而高度最多只能是较短边的高度
所以移动较长的边，容积一定会减小
但移动较短的边，可能会找到一个更高的边，容积可能增大

算法步骤（伪代码）#

初始化左右指针指向数组两端
当左右指针未相遇时：
- 计算当前容积
- 更新最大容积
- 移动较短的那条边的指针
返回最大容积

示例运行#

让我们用一个例子[1,8,6,2,5,4,8,3,7]模拟这个过程：

初始状态：left=0(高度1), right=8(高度7)
容积=min(1,7)*8=8，移动left

left=1(高度8), right=8(高度7)
容积=min(8,7)*7=49，移动right

left=1(高度8), right=7(高度3)
容积=min(8,3)*6=18，移动right

...依此类推

plaintext

Java代码实现#

public int maxArea(int[] height) {
    // maxVolume 保存当前找到的最大容积
    int maxVolume = 0;
    // left 指向左边界起点
    int left = 0;
    // right 指向右边界起点（数组最右端）
    int right = height.length - 1;

    // 当 left 与 right 未相遇时，容器宽度至少为 1，仍可继续计算
    while (left < right) {
        // 计算当前容积
        // width 是当前两条边之间的水平距离
        int width = right - left;
        // currentHeight 是当前容器可达到的有效高度（取两边较矮者）
        int currentHeight = Math.min(height[left], height[right]);
        // volume 是当前这一次计算得到的容积
        int volume = width * currentHeight;

        // 更新最大容积
        maxVolume = Math.max(maxVolume, volume);

        // 移动较短的一边
        // 原因：容积受短板限制，移动短板才有机会遇到更高的边，从而增大容积
        if (height[left] < height[right]) {
            // 左边更短，left 右移尝试提高短板高度
            left++;
        } else {
            // 右边不高于左边，right 左移尝试提高短板高度
            right--;
        }
    }

    // 返回遍历过程中的最大容积
    return maxVolume;
}

java

暴力法vs双指针法#

让我们比较这两种解法：

暴力法的时间复杂度是O(n²)，需要遍历所有可能的组合。它的优点是直观易懂，适合用来理解问题。但在处理大规模数据时效率较低。

双指针法的时间复杂度是O(n)，只需要遍历一次数组。它通过巧妙的证明，保证了不会错过最优解，同时大大提高了效率。

两种方法的空间复杂度都是O(1)，因为只需要常数级的额外空间。

题目模式总结#

这道题体现了两个重要的算法思想：

双指针技巧：通过移动两个指针来解决问题
贪心思想：每次都移动较短的边，期望找到更好的解

这种模式在很多问题中都有应用，比如：

两数之和（排序数组）
三数之和
接雨水

解决这类问题的通用思路是：

观察问题中的单调性质
寻找可以优化的搜索策略
证明优化策略的正确性

小结#

通过这道题，我们不仅学会了如何找到能盛最多水的容器，更重要的是理解了如何用双指针技巧来优化搜索过程。这种思维方式在很多算法问题中都能派上用场。

记住，解决算法问题时，不要满足于暴力解法，多思考是否存在更优雅的方案。有时候，看似复杂的问题，找到正确的思路后，解法会变得异常简单！