11. 盛最多水的容器

题目链接 (opens new window)

给定一个长度为 n 的整数数组 height 。有 n 条垂线，第 i 条线的两个端点是 (i, 0) 和 (i, height[i]) 。

找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。

返回容器可以储存的最大水量。

说明：你不能倾斜容器。

示例 1：

输入：[1,8,6,2,5,4,8,3,7]
输出：49 
解释：图中垂直线代表输入数组 [1,8,6,2,5,4,8,3,7]。在此情况下，容器能够容纳水（表示为蓝色部分）的最大值为 49。

示例 2：

输入：height = [1,1]
输出：1

提示：

• n == height.length
• 2 <= n <= 10^5^
• 0 <= height[i] <= 10^4^

思路

在这道题里，我们要从一堆竖线中选出两根，让它们和 x 轴组成的"水槽"能装最多的水。

本质上就是：
找两个下标 i、j，使 (j - i) × min(height[i], height[j]) 最大。

一开始大家可能想到暴力枚举。

最直观的想法：既然要选两根木板，那我把所有的两根木板都试一遍不就行了？

代码大概就是：

for i 从 0 到 n-1：
    for j 从 i+1 到 n-1：
        计算容量
        取最大值

时间复杂度 O(n²)，如果 n = 10⁵，直接 TLE。

计算水的容量是：(右下标 - 左下标) × min(左高度, 右高度)

想要装水多，只有两个方向：

1. 宽度更大（下标差更大）
2. 高度更高（木板高度更大）

暴力法就是所有情况全都试一遍，但我们能不能有目标地去移动下标？

我们可以从两侧开始试（也叫启发双指针）

为什么从两端开始？

因为：

• 最左和最右的组合，此时"宽度"已经是最大的了。
• 接下来想再得到更大的容量，只能依赖于 "高度" 变高。

所以我们先把两个指针放在最两侧：

l = 0
r = height.size() - 1

计算这两个位置的水容量。

此时面临一个关键决策：下一步移动哪个指针？

假设 height[l] < height[r]，那么装水高度取决于 height[l]。

因为容量由两者的最小值决定：

容量 = (r - l) * min(height[l], height[r])
     = (r - l) * height[l]  （如果左边更矮）

这时如果我们移动右指针（更高的那个）——结果能变好吗？

• 宽度变小了（r--）
• 高度的最小值仍然是 height[l]
• 所以容量一定 变小或不变，不可能变大

因此移动右指针是没有意义的！理解这一点很重要！

那我们应该移动左指针（更矮的那个）

因为：

• 或许能找到一个更高的左板
• 提高 min(height[l], height[r]) 的值
• 即使宽度减少，但如果高度大幅提升，也可能让容量变更大

盛水量由短板决定，短板不变高，容量永远不会变大。
所以要移动短板这一侧。

这样就自然得到了双指针法：

• 两端向中间收缩
• 每次移动高度较小的那一侧
• 同时更新最大容量

时间复杂度只有 O(n)。

模拟过程

拿数组 [1,8,6,2,5,4,7] 来举例，我们先将宽度调整为最大，也就是宽度为7。

此时高度取min(height[l], height[r]) ， 只能去最小值 1 ，盛水的体积也就是 7 * 1 = 7

如果想进一步扩大盛水明显，height[l] 更小，我们就向右 移动 l，看看能不能遇到一个大一些的 height[l] 这样才有可能让容器盛水更多。

l 向右移动一位之后，如图：

此时高度取min(height[l], height[r]) ， 最小值为height[r] = 6 ，宽度为6，盛水的体积也就是 6 * 6 = 36。

此时 height[r] 成为了瓶颈，再向左移动 r，看看是否能遇到更大的 height[r] 。

循环往复，直到 l 与 r 相遇为止。

代码

C++

class Solution {
public:
    int maxArea(vector<int>& height) {
        int l = 0;
        int r = height.size() - 1;
        int result = 0; // 最大水量
        while(l < r) {
            int t = (r - l) * min(height[l], height[r]); // 去盛水量 
            result = max(result, t); // 获取最大水量
            if(height[l] < height[r]) l++;
            else r--;     
        }
        return result;
    }
};

这里我直接用 max 和 min函数 是为了代码更加清晰，可读性更强，方便录友们理解。

其实在C++代码中 直接使用 max 或者 min函数是比较耗时的，大家可以换成 三元运算符，例如result = max(result, t); 换成 result = result > t ? result : t;，同时min也换了，这样效率会更高。

Python3

class Solution:
    def maxArea(self, height):
        l, r = 0, len(height) - 1
        result = 0
        while l < r:
            t = (r - l) * min(height[l], height[r])
            result = max(result, t)
            if height[l] < height[r]:
                l += 1
            else:
                r -= 1
        return result

Java

class Solution {
    public int maxArea(int[] height) {
        int l = 0;
        int r = height.length - 1;
        int result = 0;

        while (l < r) {
            int t = (r - l) * Math.min(height[l], height[r]);
            result = Math.max(result, t);

            if (height[l] < height[r]) {
                l++;
            } else {
                r--;
            }
        }
        return result;
    }
}

Go

func maxArea(height []int) int {
    l, r := 0, len(height)-1
    result := 0

    for l < r {
        t := (r - l) * min(height[l], height[r])
        if t > result {
            result = t
        }

        if height[l] < height[r] {
            l++
        } else {
            r--
        }
    }
    return result
}

func min(a, b int) int {
    if a < b {
        return a
    }
    return b
}

JS

var maxArea = function(height) {
    let l = 0, r = height.length - 1;
    let result = 0;

    while (l < r) {
        const t = (r - l) * Math.min(height[l], height[r]);
        result = Math.max(result, t);

        if (height[l] < height[r]) {
            l++;
        } else {
            r--;
        }
    }
    return result;
};

与代码随想录联系

如果大家刷过代码随想录中的双指针题目：有序数组的平方 (opens new window) ，会感觉到和本题思路是很像的。

有序数组的平方 (opens new window)** 为什么从两边？**

因为 平方后最大的值一定来自绝对值最大的元素，而绝对值最大只会出现在数组两端。

所以我们使用：

• 左指针指向最左
• 右指针指向最右
• 谁绝对值大，就把谁平方后的结果放到答案的末尾

本质还是每一步都选当前可能的最大值，所以双指针从两侧向中间收缩

而本题（盛最多水的容器）为什么也从两边？

这题虽然看起来是求"面积最大"，但其实和"有序数组的平方 (opens new window)"异曲同工：

• 最大面积一定可能由 最左 和 最右 的柱子构成
• 因为横向距离最远，能产生最大的 宽度
• 之后只需要往内收缩，看能否找到更高的柱子提升高度

所以：

• 左右双指针分别指向数组两端
• 每次计算面积后
• 移动较矮的那一根柱子

每一步都尝试当前能产生最大宽度的组合，双指针从两端向中间逼近

同时大家也可能会想到 代码随想录里的 接雨水 (opens new window) ，但其实本题比 接雨水 (opens new window) 简单多了，因为只计算一个水槽。

而接雨水 (opens new window) 是计算多个水槽。