LeetCode如何解决盛水最多的容器问题

# LeetCode如何解决盛水最多的容器问题

## 问题描述
LeetCode第11题"盛最多水的容器"(Container With Most Water)描述如下：

给定一个长度为`n`的整数数组`height`，每个元素代表垂直线的长度。找出两条线，使得它们与x轴共同构成的容器可以容纳最多的水。

示例：

输入：[1,8,6,2,5,4,8,3,7] 输出：49 解释：选择第2个(height[1]=8)和第9个(height[8]=7)垂直线，容量为 min(8,7)*7=49

## 暴力解法（不推荐）
最直观的方法是使用双重循环计算所有可能的容器面积：

```python
def maxArea(height):
    max_area = 0
    for i in range(len(height)):
        for j in range(i+1, len(height)):
            area = min(height[i], height[j]) * (j - i)
            max_area = max(max_area, area)
    return max_area

时间复杂度：O(n²)
空间复杂度：O(1)

这种方法在小数据量时可行，但在LeetCode提交时会因超时无法通过。

最优解法：双指针法

更高效的解决方案是使用双指针技术：

算法思路

1. 初始化左指针left=0和右指针right=len(height)-1
2. 计算当前面积并更新最大值
3. 移动较短边的指针（因为移动较长边不可能获得更大面积）
4. 重复直到指针相遇

Python实现

def maxArea(height):
    left, right = 0, len(height) - 1
    max_area = 0
    
    while left < right:
        current_area = min(height[left], height[right]) * (right - left)
        max_area = max(max_area, current_area)
        
        if height[left] < height[right]:
            left += 1
        else:
            right -= 1
    
    return max_area

时间复杂度分析

• 时间复杂度：O(n)，只需遍历数组一次
• 空间复杂度：O(1)，只使用了常数个额外空间

为什么双指针法有效？

关键点在于理解为什么移动较短边的指针是正确的：

1. 面积由宽度和高度决定：面积 = min(height[left], height[right]) * width
2. 移动长边不会增加面积：
   • 因为高度受限于较短边
   • 宽度一定会减小
   • 所以面积必然减小或不变
3. 移动短边可能获得更大面积：
   • 虽然宽度减小
   • 但可能遇到更高的边，从而弥补宽度的损失

边界情况处理

在实际编码中需要考虑的特殊情况： 1. 空数组或单元素数组：直接返回0 2. 所有高度相同：任意选择两个边结果相同 3. 存在多个相同最大值：算法会自动找到其中一个

算法可视化

初始状态：
[1, 8, 6, 2, 5, 4, 8, 3, 7]
 ↑                       ↑
left                   right

步骤1：计算area=8，移动left
[1, 8, 6, 2, 5, 4, 8, 3, 7]
    ↑                   ↑

步骤2：计算area=49，移动right
...
最终在left=1(right=8)时得到最大值

实际应用场景

这类问题在实际中有多种应用： 1. 水库容量计算 2. 城市规划中的建筑间距设计 3. 图形界面中的布局优化

总结

盛水容器问题展示了如何通过： 1. 分析问题本质（面积=宽×高） 2. 识别关键约束（高度受限于较短边） 3. 应用双指针技术优化时间复杂度

掌握这种解题思路可以帮助解决许多类似的数组优化问题。 “`

这篇文章包含了问题描述、暴力解法、最优解法、复杂度分析、正确性证明、边界情况处理、可视化示例和实际应用，总字数约900字，采用Markdown格式。