盛最多水的容器
2025年10月28日大约 7 分钟教学文档动态规划
题目描述
题目分析
盛最多水的容器问题分析
题目理解
我们需要在n条垂线中选择两条，与x轴构成一个容器，使得容器能装的水最多。
容器容量计算公式：
- 宽度 = 两线之间的距离 =
j - i（假设j > i） - 高度 = 两线中较短的高度 =
min(height[i], height[j]) - 容量 = 宽度 × 高度 =
(j - i) * min(height[i], height[j])
贪心策略分析
直观思路 vs 贪心思路
错误的直观思路：选择最高的两条线
- 反例：
[1, 8, 6, 2, 5, 4, 8, 3, 7]，最高的是8和8，但最优解是8和7
正确的贪心策略：双指针法
- 初始化：左指针在最左端(i=0)，右指针在最右端(j=n-1)
- 计算当前容量，并更新最大值
- 关键决策：移动较短的那条线的指针
为什么移动较短的线是正确的？
证明思路（贪心选择性质）：
假设当前左指针i，右指针j，且height[i] <= height[j]
如果移动较高的线（j向左移动）：
- 新宽度：
(j-1) - i < j - i（宽度减小） - 新高度：
min(height[i], height[j-1]) <= height[i]（高度不会超过原来的较短线） - 结果：容量一定不会比当前更大
- 新宽度：
如果移动较短的线（i向右移动）：
- 新宽度：
j - (i+1) < j - i（宽度减小） - 新高度：
min(height[i+1], height[j])可能大于height[i] - 结果：虽然宽度减小，但高度可能增加，总体容量可能更大
- 新宽度：
结论：只有移动较短的线，才有可能找到更大的容量。
算法正确性保证
- 不会遗漏最优解：每次移动都排除了不可能产生更优解的情况
- 覆盖所有可能：双指针最终会相遇，遍历了所有有意义的组合
- 贪心选择安全：每次选择都是局部最优且不影响全局最优
算法步骤
- 初始化双指针：
left = 0,right = n-1 - 初始化最大容量：
max_area = 0 - 当
left < right时循环：- 计算当前容量：
(right - left) * min(height[left], height[right]) - 更新最大容量
- 移动较短边的指针
- 计算当前容量：
- 返回最大容量
时间复杂度分析
- 时间复杂度：O(n) - 每个元素最多被访问一次
- 空间复杂度：O(1) - 只使用常数额外空间
Python代码实现
def maxArea(height):
"""
计算盛最多水的容器的最大容量
Args:
height: List[int] - 垂线的高度数组
Returns:
int - 最大容量
"""
if not height or len(height) < 2:
return 0
left = 0
right = len(height) - 1
max_area = 0
while left < right:
# 计算当前容器的容量
width = right - left
current_height = min(height[left], height[right])
current_area = width * current_height
# 更新最大容量
max_area = max(max_area, current_area)
# 贪心策略：移动较短的边
if height[left] < height[right]:
left += 1
else:
right -= 1
return max_area
# 测试用例
if __name__ == "__main__":
# 测试用例1
height1 = [1, 8, 6, 2, 5, 4, 8, 3, 7]
print(f"输入: {height1}")
print(f"输出: {maxArea(height1)}") # 期望输出: 49 (第2条线和最后一条线)
# 测试用例2
height2 = [1, 1]
print(f"输入: {height2}")
print(f"输出: {maxArea(height2)}") # 期望输出: 1
# 测试用例3
height3 = [4, 3, 2, 1, 4]
print(f"输入: {height3}")
print(f"输出: {maxArea(height3)}") # 期望输出: 16
# 测试用例4
height4 = [1, 2, 1]
print(f"输入: {height4}")
print(f"输出: {maxArea(height4)}") # 期望输出: 2
# 边界测试
height5 = [1]
print(f"输入: {height5}")
print(f"输出: {maxArea(height5)}") # 期望输出: 0
算法执行过程示例
以[1, 8, 6, 2, 5, 4, 8, 3, 7]为例：
初始: left=0(1), right=8(7), area=8*1=8, max_area=8
移动left → left=1(8), right=8(7), area=7*7=49, max_area=49
移动right → left=1(8), right=7(3), area=6*3=18, max_area=49
移动right → left=1(8), right=6(8), area=5*8=40, max_area=49
移动left或right → ... (继续直到指针相遇)
最终结果: 49
这个贪心算法通过双指针策略，巧妙地避免了O(n²)的暴力枚举，实现了线性时间复杂度的最优解。
注意事项与题目启发
需要注意的问题
1. 边界条件处理
if not height or len(height) < 2:
return 0
- 数组为空或只有一个元素时，无法构成容器
- 必须确保至少有两条线才能形成容器
2. 双指针移动逻辑的正确性
- 关键点：必须移动较短的那条线，而不是任意移动
- 常见错误：移动较长的线，这样会错过最优解
- 相等情况：当两条线高度相等时，移动任意一个都可以（代码中移动右指针）
3. 整数溢出问题
- 虽然Python不会溢出，但在C++/Java等语言中，
width * height可能超出int范围 - 实际应用中应使用long类型存储面积
4. 算法理解误区
- 不是简单的"找最高两条线"：宽度和高度需要平衡
- 不是动态规划问题：虽然看起来有最优子结构，但贪心策略更优
- 时间复杂度认知：O(n)解法依赖于贪心性质，不是所有类似问题都有线性解
5. 指针移动的终止条件
- 循环条件必须是
left < right，不能是left <= right - 当指针相遇时，宽度为0，无法构成有效容器
6. 测试用例覆盖
需要考虑多种情况：
- 递增序列：
[1,2,3,4,5] - 递减序列：
[5,4,3,2,1] - 相同高度：
[3,3,3,3] - 极端值：
[1,1000000,1]
题目的启发
1. 贪心算法的巧妙应用
- 反直觉的贪心选择：通常贪心是"选大的"，但这里是"放弃小的"
- 证明的重要性：贪心策略必须有严格的正确性证明，不能仅凭直觉
- 局部最优导向全局最优：每次放弃较短线都不会错过最优解
2. 双指针技术的精髓
- 状态空间压缩：从O(n²)的二维搜索空间压缩到O(n)的一维路径
- 决策单调性：指针只向一个方向移动，不会回溯
- 通用模式：适用于许多"两端向中间收敛"的问题
3. 问题建模的数学思维
- 目标函数分析：
area = width × min(height1, height2) - 约束条件识别：宽度和高度存在此消彼长的关系
- 极值分析：理解何时可能达到最大值
4. 算法设计的层次思考
这个问题展示了不同解法的演进：
- 暴力解法：O(n²) 枚举所有组合
- 优化思路：分析哪些组合可以安全跳过
- 贪心解法：O(n) 双指针，基于数学证明
5. 实际应用价值
- 工程优化：在资源分配、负载均衡等问题中，经常需要在多个约束间找平衡
- 决策制定：现实中的很多决策都需要在"数量"和"质量"间权衡
- 系统设计：理解瓶颈因素（短板效应）对系统性能的影响
6. 编程思维的培养
- 从具体到抽象：将几何问题转化为数学公式
- 反例验证：通过构造反例来验证或推翻直觉
- 证明驱动开发：先证明算法正确性，再实现代码
7. 扩展思考方向
这个问题可以引申出更多变种：
- 三维版本：在三维空间中找最大体积
- 动态版本：高度数组动态变化，需要实时维护最大面积
- 多容器版本：选择k对线形成k个不重叠容器
- 约束版本：某些位置不能选择，或有额外成本
8. 面试价值
- 经典程度：这是LeetCode最经典的双指针题目之一
- 考察维度：既考察算法思维，又考察数学证明能力
- 延伸性强：可以自然过渡到其他双指针或贪心问题
这个题目完美诠释了"简单问题蕴含深刻思想"的道理，看似直观的问题背后需要严谨的数学分析和算法设计思维。