.jpg)
522 字
3 分钟
盛最多水的容器
题目描述
给定一个长度为 n 的整数数组 height 。有 n 条垂线，第 i 条线的两个端点是 (i, 0) 和 (i, height[i]) 。
找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。
返回容器可以储存的最大水量。
**说明：**你不能倾斜容器。
解题思路
- 双指针逼近：
- 初始化左右指针分别指向数组首尾
- 计算当前容量：
min(height[left], height[right]) * (right-left) - 更新最大容量记录
- 指针移动策略：
- 移动高度较小的指针（短板效应）
- 较小高度决定容量上限
- 收敛扫描：
- 指针向中心收敛直至相遇
- 每次移动都尝试提升短板高度
- 数学原理：
- 宽度递减时，只有增大高度才能提升容量
- 较高端固定时移动低端更优
关键洞察
- 短板效应：
- 容器容量由较短边决定
- 移动长边无法增加容量
- 宽度-高度平衡：
- 初始最大宽度优先
- 牺牲宽度换取高度提升
- 决策最优性证明：
- 每次移动都保证不错过最优解
- 扫描过程覆盖所有潜在最优组合
- 无后效性：
- 指针移动只依赖当前状态
- 无需回溯历史位置
复杂度分析
| 指标 | 说明 |
|---|---|
| 时间复杂度 | O(n)：左右指针共遍历n个元素 |
| 空间复杂度 | O(1)：仅使用常数额外变量 |
代码实现
var maxArea = function (height) { let l = 0, r = height.length - 1; let maxWater = 0;
while (l < r) { const hl = height[l], hr = height[r]; // 计算当前容器水量 const currentWater = Math.min(hl, hr) * (r - l); maxWater = Math.max(maxWater, currentWater);
// 跳过无法增加面积的情况 if (hl < hr) { // 移动左指针直到找到更高的柱子 while (l < r && height[l] <= hl) l++; } else { // 移动右指针直到找到更高的柱子 while (l < r && height[r] <= hr) r--; } }
return maxWater;};