LeetCode 热题 100 之 11.盛最多水的容器
·

方法
采用左右双指针夹逼的方式,从数组两端向中间遍历,逐步缩小范围,同时记录遍历过程中的最大面积,步骤如下:
- 初始化指针和最大面积:左指针
left指向数组起始位置(0),右指针right指向数组末尾位置(n-1),最大面积maxArea初始值为 0; - 双指针夹逼遍历:当
left < right时,循环执行以下操作:- 计算当前容器的盛水量:用公式
(right - left) × Math.min(height[left], height[right]); - 更新最大面积:如果当前盛水量大于
maxArea,则将maxArea替换为当前值; - 移动较矮的指针(核心技巧):
- 若
height[left] < height[right],左指针右移(因为矮边在左,此时移动高边(右)只会让宽度变小,盛水量不可能增加;只有移动矮边,才有可能找到更高的边,让盛水量变大); - 反之,右指针左移(同理,矮边在右,移动右指针才有可能提升高度);
- 若
- 计算当前容器的盛水量:用公式
- 返回结果:当左右指针相遇(
left >= right)时,循环结束,此时maxArea就是容器能容纳的最大水量。
通俗理解核心技巧
“矮边决定水量,移动矮边才有机会变大”,高边留在原地即可,避免无效的遍历,让整个过程只需要一次数组扫描。
示例验证(输入 [1,8,6,2,5,4,8,3,7])
- 初始:left=0(高度 1)、right=8(高度 7),面积 = 8×1=8,maxArea=8 → 左矮,左指针右移至 1;
- left=1(8)、right=8(7),面积 = 7×7=49,maxArea=49 → 右矮,右指针左移至 7;
- 后续持续移动较矮的指针,所有计算出的面积都小于 49,最终 maxArea=49,与示例输出一致。
代码实现
class Solution {
public int maxArea(int[] height) {
int left = 0; // 左指针
int right = height.length - 1; // 右指针
int maxArea = 0; // 最大盛水量
while (left < right) {
// 计算当前面积
int curWidth = right - left;
int curHeight = Math.min(height[left], height[right]);
int curArea = curWidth * curHeight;
// 更新最大面积
if (curArea > maxArea) {
maxArea = curArea;
}
// 移动较矮的指针
if (height[left] < height[right]) {
left++;
} else {
right--;
}
}
return maxArea;
}
}
总结
- 盛水量核心公式:
面积 = 左右指针间距 × 左右高度的较小值; - 最优解法为双指针夹逼法,从两端向中间遍历,移动较矮的指针是核心;
- 时间复杂度 O (n)、空间复杂度 O (1),适配题目大数据量要求。
- 希望能帮助到你,谢谢!
更多推荐



所有评论(0)