当前位置：首页 > news >正文

【LeetCode 热题 100】盛最多水的容器

news 2026/5/28 17:04:21

精选专栏链接 🔗

LeetCode hot 100系列专栏
MySQL技术笔记专栏
Redis技术笔记专栏
消息中间件专栏
大模型搭建专栏
Python学习笔记专栏
深度学习算法专栏

欢迎订阅，点赞＋关注，每日精进1%，与百万开发者共攀技术珠峰

更多内容持续更新中~

【LeetCode 热题 100】盛最多水的容器

📝题目描述
💡提示信息
核心分析：面积如何计算？
解法一：暴力枚举法
解法二：双指针法（最优解）
- 为什么移动较短的那根柱子？（数学证明）
总结

📝题目描述

给定一个长度为 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 10^5105；
0 <= height[i] <=10 4 10^4104；

核心分析：面积如何计算？

我们要找的是最大面积。假设我们选择了两条线，索引分别为i ii和j jj（假设i < j i < ji<j），它们的高度分别为h e i g h t [ i ] height[i]height[i]和h e i g h t [ j ] height[j]height[j]。

容器的面积公式为：
A r e a = 宽度 × 高度 Area = \text{宽度} \times \text{高度}Area=宽度×高度
A r e a = ( j − i ) × min ⁡ ( h e i g h t [ i ] , h e i g h t [ j ] ) Area = (j - i) \times \min(height[i], height[j])Area=(j−i)×min(height[i],height[j])

这意味着，容器的盛水量取决于两个因素：

底边的宽度：两根柱子的距离；
短板的高度：两根柱子中较短的那一根（木桶效应）；

解法一：暴力枚举法

暴力枚举法是最直观的思路是，需要尝试所有的组合：

外层循环从第 1 根柱子开始；
内层循环遍历该柱子后面的所有柱子；
计算每一对组合的面积，并更新最大值；

Java 代码实现

classSolution{publicintmaxArea(int[]height){intmaxArea=0;for(inti=0;i<height.length;i++){for(intj=i+1;j<height.length;j++){intwidth=j-i;inth=Math.min(height[i],height[j]);maxArea=Math.max(maxArea,width*h);}}returnmaxArea;}}

提交代码，运行结果如下：

时间复杂度：O ( N 2 ) O(N^2)O(N2)。我们需要计算N ( N − 1 ) / 2 N(N-1)/2N(N−1)/2对组合；
空间复杂度：O ( 1 ) O(1)O(1)；

此方式逻辑上行得通，但是数组很大时，此方法会超时，因此不推荐使用，更推荐使用双指针法实现。

解法二：双指针法（最优解）

为了优化时间复杂度，我们需要一种更聪明的方法来排除不必要的计算。这就是双指针法。

算法思路

初始化两个指针：left指向数组头部（0），right指向数组尾部（n-1）。此时宽度最大；
计算当前left和right围成的面积，并更新最大面积；
关键步骤：移动指针。（移动较短的柱子）
- 如果height[left] < height[right]，则移动left（left++）。
- 如果height[left] >= height[right]，则移动right（right--）。
重复步骤 2 和 3，直到left和right相遇。

为什么移动较短的那根柱子？（数学证明）

这是本题最难理解也最精彩的地方。假设当前height[left] < height[right]。此时面积S = h e i g h t [ l e f t ] × ( r i g h t − l e f t ) S = height[left] \times (right - left)S=height[left]×(right−left)。

如果我们移动较高的柱子（即right--）：

宽度( r i g h t − l e f t ) (right - left)(right−left)必然减小；
高度取决于min ⁡ ( h e i g h t [ l e f t ] , h e i g h t [ n e w _ r i g h t ] ) \min(height[left], height[new\_right])min(height[left],height[new_right])。因为高度受限于较短的 height[left]，无论 new_right多高，最终使用的高度都不可能超过 height[left]。
结论：移动较高的柱子时，宽度变小，高度不变或变小→ \rightarrow→面积一定变小。

反之，如果我们移动较短的柱子（即left++）：

宽度( r i g h t − l e f t ) (right - left)(right−left)必然减小；
但是，新的高度height[new_left]可能会比原来的height[left]更高，从而可能抵消宽度的损失，甚至获得更大的面积。

一句话总结：只有移动短板，才有可能在宽度减小的情况下，通过增加高度来获得更大的面积。

Java 代码实现如下：

publicclassSolution{publicintmaxArea(int[]height){intleft=0;intright=height.length-1;intmaxArea=0;while(left<right){// 计算当前面积// 宽度是 right - left// 高度取两者的较小值intcurrentArea=Math.min(height[left],height[right])*(right-left);// 更新最大面积maxArea=Math.max(maxArea,currentArea);// 移动指针策略：谁短移谁if(height[left]<height[right]){left++;}else{right--;}}returnmaxArea;}}

运行结果如下：

进一步优化代码：

classSolution{publicintmaxArea(int[]height){intmax=0;// 使用局部变量缓存数组长度intlen=height.length;// 双指针intleft=0;intright=len-1;while(left<right){// 1. 缓存当前高度，避免重复访问数组inthLeft=height[left];inthRight=height[right];// 2. 计算宽度intwidth=right-left;// 3. 计算高度和移动指针if(hLeft<hRight){// 左边矮，用左边算面积，左指针右移// 三元运算符替换原有 Math.min/Math.maxintarea=hLeft*width;max=area>max?area:max;left++;}else{// 右边矮（或相等），用右边算面积，右指针左移intarea=hRight*width;if(area>max)max=area;right--;}}returnmax;}}