11、盛最多水的容器

鲁迅说过，读书

不觉

已春

深

，一

寸光阴一寸金。如果你每 天

只刷一道 题，那么你

离大厂只有 300 天的距离。如果你每天刷两道题，那么你离大厂只有 150 天的距离。（?）

题意

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

height[i]) 。

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

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

说明：你不能倾斜容器。

难度

中等

示例

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

输出：49

解释：图中垂直线代表输入数组 [1,8,6,2,5,4,8,3,7]。i 取 1，j 取 8，分别对应的 a[i]为 8，a[j]

为 7，所以答案为 7 * （8 - 1） = 49，也就是说，在此情况下，容器能容纳（下图中蓝色部

分）的最大值为 49。

011.%E7%9B%9B%E6%9C%80%E5%A4%9A%E6%B0%B4%E7%9A%84%E5%AE%B9%E

5%99%A8-20240120115841.png

分析 1

这道题很容易想到两个 for 循环，外层循环遍历所有可能的左边界，内层循环遍历所有可

能的右边界，然后计算当前两个边界能形成的容器的水容量，并更新最大值。

class Solution {

public int maxArea(int[] height) {

int res = 0; // 初始化结果变量，用来存储最大水容量

// 外层循环遍历所有可能的左边界

for (int i = 0; i < height.length; i++) {

// 内层循环遍历所有可能的右边界

for (int j = i + 1; j < height.length; j++) {

// 计算当前两个边界能形成的容器的水容量，并更新最大值

// (j - i) 是宽度，Math.min(height[i], height[j]) 是高度

res = Math.max(res, (j - i) * Math.min(height[i], height[j]));

}

}

return res; // 返回计算得到的最大水容量

}

}

对于每一对边界，使用 (j - i) 来计算宽度，Math.min(height[i], height[j]) 来计算高度

（容器的水高由两边界中较短的那个决定）。

计算当前这对边界可以形成的容器的水容量，并与之前的最大值进行比较，最终得到最大

水容量。

思路很简单，两个 for 循环，外加 Math.max() 和 Math.min() 两个静态方法，就能够解

决这道题。

但很遗憾，效率太低，直接超出了时间限制。

011.%E7%9B%9B%E6%9C%80%E5%A4%9A%E6%B0%B4%E7%9A%84%E5%AE%B9%E

5%99%A8-20240120120552.png

分析 2

之所以超时，原因就在于我们用了两个 for 循环，这样的话，时间复杂度就是 $ O(n^2) $

了，我们需要想办法优化这个时间复杂度。

我们可以使用双指针来优化这个时间复杂度，一个指向数组的头部，一个指向数组的尾

部，然后我们计算当前两个指针所指向的边界能形成的容器的水容量，并更新最大值。

class Solution {

public int maxArea(int[] height) {

int maxArea = 0; // 用于存储最大水容量

int left = 0; // 初始化左指针

int right = height.length - 1; // 初始化右指针

while (left < right) {

int currentArea = (right - left) * Math.min(height[left], height[right]); // 计算

容量

maxArea = Math.max(maxArea, currentArea); // 更新最大水容量

if (height[left] < height[right]) {

left++; // 如果左边较短，向右移动左指针

} else {

right--; // 如果右边较短，向左移动右指针

}

}

return maxArea; // 返回最大水容量

}

}

核心算法和之前差不多，都用到了 Math.max() 和 Math.min() 两个静态方法，但是这里

使用了双指针，时间复杂度就变成了 $ O(n) $。

其核心关键点在于，我们每次都移动较短的那个指针，这是因为容器的高度由较短的边界

决定，而移动较长的边界不会增加容器的高度。

011.%E7%9B%9B%E6%9C%80%E5%A4%9A%E6%B0%B4%E7%9A%84%E5%AE%B9%E

5%99%A8-20240120121723.png

我们来推理一下，以 [1,8,6,2,5,4,8,3,7] 为例，假设我们初始化左指针 left = 0，右指针

right = 8，那么此时容器的水容量为 min(1, 7) * (8 - 0) = 8。

由于 height[left] < height[right]，所以我们移动左指针，此时 left = 1，右指针不变，

容器的水容量为 min(8, 7) * (7 - 1) = 49。

此时，由于 height[left] > height[right]，所以我们移动右指针，此时 left = 1，右指针

right = 7，容器的水容量为 min(8, 3) * (7 - 1) = 24。

依次类推，我们最终得到最大水容量为 49。

由此可见，双指针比两个 for 循环的效率要高得多，因为只需要遍历一次数组，但可以巧

妙地移动两个指针，就相当于原来你用一只手去搬了两次东西，现在你用两只手去搬一次

东西，效率自然就提高了。

011.%E7%9B%9B%E6%9C%80%E5%A4%9A%E6%B0%B4%E7%9A%84%E5%AE%B9%E

5%99%A8-20240120122614.png

虽然没有 beat 100%，但是双指针

的优化空间

已经很小了，大家如果有更好的题

解思路，可以在评

区留言，我们

论 一起讨

论

（

）

。

总结

这道题和 Java 基础相关的内容就两块：

• for 循环、while 循环和 if 语句

• Math 类，大家可以自己去看看 Math 类的源码，里面有很多常用的数学方法。

011.%E7%9B%9B%E6%9C%80%E5%A4%9A%E6%B0%B4%E7%9A%84%E5%AE%B9%E

5%99%A8-20240120123833.png

力扣链接：https://leetcode.cn/problems/container-with-most-water/