LeetCode 11. 盛最多水的容器
题目描述
题意分析
从数组中选择两个不同下标作为容器的左右边界，返回能够容纳的最大水量。两条竖线之间的距离是宽度，较矮竖线的高度是水位上限，因此选择
left、right时，面积为(right - left) × min(height[left], height[right])。只计算选定两条边形成的整体面积，中间的竖线不参与扣减，也不需要逐个位置累加积水。竖线的位置不能改变，所以不能按高度排序；返回面积即可，不需要返回两条边的下标。
解法：双指针移动短板
核心思路
[!blue]
若枚举所有边界对，需要平方时间。双指针从数组两端开始，每次计算当前面积，再排除一个不可能带来更优答案的端点，使剩余搜索范围逐步缩小。
假设
height[left] <= height[right]，当前面积的高度就是height[left]。如果保留left，把右边界改成区间内任意更靠左的位置，宽度一定变小，高度又不可能超过height[left]，新面积就不可能大于当前面积。当前组合已经参与最大值比较，因此所有仍以
left为左边界的剩余组合都可以放弃，直接执行left++。右端更矮时完全对称，执行right--；两端等高时，两边都满足这个排除依据，移动任意一端即可，代码选择移动右端。每次删去的候选都不优于已经记录的面积，所以没有逐对枚举也不会漏掉最大值。移动短板只是保留变得更优的可能，并不保证下一次面积一定增大；需要用
ans始终保存历史最大值，直到两个指针相遇。
解题步骤
- 令
left = 0、right = n - 1，从最大宽度开始。- 在
left < right时，计算当前面积并更新最大值；必须先计算，再移动指针。- 比较两端高度，移动较矮的一端；相等时任选一端移动。
- 指针相遇后返回最大面积。
代码实现
class Solution {
public int maxArea(int[] height) {
int left = 0;
int right = height.length - 1;
int ans = 0;
while (left < right) {
int minHeight = Math.min(height[left], height[right]);
ans = Math.max(ans, (right - left) * minHeight);
// 宽度变小后，只有移动短板才可能找到更大面积。
if (height[left] < height[right]) {
left++;
} else {
right--;
}
}
return ans;
}
}
func maxArea(height []int) int {
left := 0
right := len(height) - 1
ans := 0
for left < right {
h := height[left]
if height[right] < h {
h = height[right]
}
area := (right - left) * h
if area > ans {
ans = area
}
// 固定较矮端再缩小宽度不会更优，因此排除短板这一端。
if height[left] < height[right] {
left++
} else {
right--
}
}
return ans
}
复杂度分析
- 时间复杂度：$O(n)$。每轮至少有一个指针向内移动，总共至多移动
n - 1次。- 空间复杂度：$O(1)$。
关键点总结
[!green]
- 固定较矮边时，剩余组合的宽度更小、高度上限不变，所以可以一次排除这些组合。
- 先记录当前面积，再排除短板；
ans保存所有已检查组合中的最大值。- 高度相等也能安全排除一端，无需额外搜索分支。
易错点总结
[!yellow]
- 移动较高的一端会直接放弃这条高边，但它仍可能与内部更高的边组成更优答案，因此没有安全排除的依据。
- 宽度是两条线的坐标差
right - left，不是区间内元素个数right - left + 1。- 必须先计算当前面积再移动短板，否则可能漏掉最优边界对；数组只有两条线时也要计算一次。
- 当前面积并不单调，不能因一次下降就提前结束。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 42. 接雨水 | 困难 | 同样由高度限制蓄水，本题只选两条边并计算容器面积，原题每个位置可被多条柱子围住。 |
| 15. 三数之和 | 中等 | 同样先证明移动某一端不会丢掉更优解，三数之和依据有序和，本题依据较短边限制。 |
转载与许可
许可
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！