盛最多水的容器
Container With Most Water
本机进度仅保存在当前浏览器
题目描述
给定一个长度为 n 的整数数组 height，第 i 条竖线两端位于 (i, 0) 与 (i, height[i])。任选两条竖线与 x 轴构成容器，水量 = 两线间距 × 较短线的高度，求最大水量。
示例：height = [1, 8, 6, 2, 5, 4, 8, 3, 7]，选第 2 与第 9 条线，输出 49。
解题思路
- 暴力枚举两条线是 O(n^2)；双指针从两端开始，每步只移动较短的板。
- 缩小区间必然使宽度变小，若移动较长的板，高度上限不变或更小，水量只会更差——可以安全排除。
- 因此每次淘汰短板是"不丢最优解"的收缩，左右指针相遇前记录的面积最大值即为答案。
参考实现
查看参考实现Python · 建议先自行作答
def maxArea(height):
# 双指针向内收缩，每次移动较短的一侧
l, r, best = 0, len(height) - 1, 0
while l < r:
best = max(best, (r - l) * min(height[l], height[r]))
if height[l] < height[r]:
l += 1
else:
r -= 1
return best