力扣hot100:盛最多水的容器：双指针法高效求解最大容量问题(11)

今天我将分享LeetCode上经典的"盛最多水的容器"问题（第11题）的解法。

问题描述

核心思路：双指针夹逼策略

关键洞察：容器的盛水量由两个因素决定：

1. 容器宽度（两指针距离）
2. 容器高度（两垂直线中较短的那个）

我们使用双指针法从两端向中间移动：

• 左指针left从0开始
• 右指针right从末尾开始
• 每次移动较短的垂直线对应的指针（因为移动较长的线不可能增加容量）

代码实现

public int maxArea(int[] height) {int ans = 0;                // 存储最大容量int left = 0;               // 左指针int right = height.length - 1; // 右指针while (left < right) {// 计算当前容器容量int ansTemp = (right - left) * Math.min(height[left], height[right]);// 更新最大容量ans = Math.max(ans, ansTemp);// 关键决策：移动较短的垂直线if (height[left] <= height[right]) {left++;} else {right--;}}return ans;
}

算法解析

1. 指针移动策略

• 当height[left] <= height[right]时，左指针右移
• 当height[left] > height[right]时，右指针左移

为什么这样移动正确？ 移动较短的线可能遇到更高的线，从而增加容量；而移动较长的线只会使宽度减小，且高度受限于更短的线，容量不可能增加。

2. 实例推演

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

1. [1, ... ,7] -> 容量: 1*8=8 → 移动左指针 
2. [8, ... ,7] -> 容量: 7*7=49 → 更新最大值 
3. 移动右指针（8>7？不成立，实际8<7？注意比较的是当前位置的值） ...继续移动直到找到最大值

复杂度分析

• 时间复杂度：O(n)，仅需遍历数组一次
• 空间复杂度：O(1)，仅使用常数级额外空间

关键点说明

1. 贪心思想：每次移动都尝试寻找可能增加容量的机会
2. 决策依据：总是移动较短的线，因为这是唯一可能增加容量的方向
3. 边界处理：循环条件left < right保证指针不会越界

优化思考

虽然代码已很简洁，但可以进一步优化：

// 小优化：跳过不可能增加容量的垂直线 
while (left < right && height[left] <= height[newLeft]) { left++; }

实际测试中，原始代码已足够高效，在LeetCode上超过95%的Java提交。

实际应用

这种双指针方法不仅适用于此问题，还可用于：

1. 两数之和（有序数组）
2. 三数之和
3. 接雨水问题
4. 任何需要从两端向中间扫描的场景

总结

通过这道题，我们学习到：

1. 双指针法在空间效率上的优势
2. 贪心策略在优化问题中的应用
3. 如何将几何问题转化为高效的算法实现

核心启示：当问题存在对称性时，从两端同时向中间推进往往能获得最优解。这种思路在解决数组类问题时非常有效。