11. 盛最多水的容器
最新回答
暗中人
2026-04-30 06:06:06
盛最多水的容器问题可以通过双指针法高效解决。以下是详细解答：
核心思路- 问题本质：给定一个数组 height，每个元素表示一条垂直线的高度。找到两条线，使得它们与 x 轴构成的容器能容纳最多的水。
- 关键观察：容器的水量由两条线之间的距离（宽度）和两条线中较短的那条的高度（高度）决定。公式为：面积 = min(height[left], height[right]) × (right - left)。
初始化指针：
左指针 left 指向数组起始位置（0）。
右指针 right 指向数组末尾（height.length - 1）。
初始化最大面积 maxArea = 0。
循环移动指针：
计算当前容器的面积，并更新 maxArea。
移动较短边的指针：
如果 height[left] < height[right]，则 left++（因为移动较长的边不会增加面积）。
否则，right--。
终止条件：left >= right。
返回结果：
最终 maxArea 即为最大水量。
- 避免重复计算：暴力法会枚举所有可能的线对（O(n2)），而双指针法通过每次移动较短边的指针，跳过不可能成为最大面积的组合。
- 数学证明：
假设 height[left] < height[right]，此时面积为 height[left] × (right - left)。
如果移动 right 指针（较长边），新面积的宽度减小，而高度受限于 height[left]（更短的边），因此面积必然减小。
只有移动 left 指针（较短边），才可能遇到更高的线，从而可能增大面积。
- 时间复杂度：O(n)，仅需一次遍历。
- 空间复杂度：O(1)，仅使用常数空间。
以 height = [1,8,6,2,5,4,8,3,7] 为例：
- 初始：left=0（高度1），right=8（高度7），面积=min(1,7)×8=8。
- 移动 left（1 < 7），left=1（高度8），面积=min(8,7)×7=49。
- 移动 right（8 > 7），right=7（高度3），面积=min(8,3)×6=18。
- 移动 right（8 > 3），right=6（高度8），面积=min(8,8)×5=40。
- 移动 left（8 == 8），left=2（高度6），面积=min(6,8)×4=24。
- 依此类推，最终最大面积为 49。
双指针法通过贪心策略（每次移动较短边的指针）高效地缩小搜索范围，确保在 O(n) 时间内找到最优解。这种方法适用于类似“需要同时考虑两端”的问题（如接雨水、三数之和等）。
热门标签
