1 / 4思路
Container With Most Water
思路
面积由两端中较短的一条边和宽度决定。左右指针从两端向中间收:每次移动较短的那条边。移动长边不会让面积变大,因为宽度减小而高度受短边限制。
复杂度
- 时间 O(n):两个指针各走一遍。
- 空间 O(1)。
代码
- Python
- TypeScript
def max_area(height: list[int]) -> int:
left, right = 0, len(height) - 1
best = 0
while left < right:
width = right - left
area = width * min(height[left], height[right])
best = max(best, area)
if height[left] < height[right]:
left += 1
else:
right -= 1
return best
function maxArea(height: number[]): number {
let left = 0;
let right = height.length - 1;
let best = 0;
while (left < right) {
const area = (right - left) * Math.min(height[left], height[right]);
best = Math.max(best, area);
if (height[left] < height[right]) left += 1;
else right -= 1;
}
return best;
}
边界
- 少于两条边:无法形成容器,返回 0。
- 两边等高:移动任意一边都可以,面积已由当前宽度决定。
- 高度为 0:面积为 0,不影响指针继续收缩。