如何编写代码实现盛最多水的容器

# 如何编写代码实现盛最多水的容器

## 问题描述

给定一个长度为 `n` 的非负整数数组 `height`，其中每个元素代表坐标轴上的一个点 `(i, height[i])`。我们需要找到两条垂直线，使得它们与x轴共同构成的容器可以容纳最多的水。

![盛水容器示意图](https://aliyun-lc-upload.oss-cn-hangzhou.aliyuncs.com/aliyun-lc-upload/uploads/2018/07/25/question_11.jpg)

*示意图说明：红色垂直线代表选定的两条线，阴影部分代表可以盛放的水量*

## 问题分析

### 关键要素
1. **容器边界**：由数组中的两个元素决定
2. **容器高度**：由两个边界中较矮的那个决定
3. **容器宽度**：两个边界在数组中的索引之差
4. **盛水量公式**：`min(height[left], height[right]) * (right - left)`

### 示例
```python
输入：[1,8,6,2,5,4,8,3,7]
输出：49 
解释：选择第2个（高度8）和第9个（高度7）的线，盛水量 = min(8,7) * (7-1) = 7 * 7 = 49

解决方案

1. 暴力解法（Brute Force）

算法思路

• 枚举所有可能的容器组合
• 计算每个组合的盛水量
• 记录最大值

代码实现

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

复杂度分析

• 时间复杂度：O(n²) - 双重循环
• 空间复杂度：O(1) - 只使用常数空间

2. 双指针法（最优解）

算法思路

1. 初始化两个指针分别指向数组的首尾
2. 计算当前容器的盛水量
3. 移动高度较小的指针（因为移动较高的指针不可能得到更大的面积）
4. 重复直到指针相遇

正确性证明

• 贪心选择性质：每次移动较矮的指针是局部最优选择
• 不会错过最优解：由于面积受限于较矮的边界，移动较高的边界不会增加面积

代码实现

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

复杂度分析

• 时间复杂度：O(n) - 单次遍历
• 空间复杂度：O(1) - 常数空间

算法优化

优化点1：提前终止

当剩余宽度乘以当前最大可能高度（数组中的最大值）小于已获得的最大面积时，可以提前终止。

def maxArea_optimized(height):
    left, right = 0, len(height) - 1
    max_area = 0
    max_h = max(height)
    while left < right:
        area = min(height[left], height[right]) * (right - left)
        max_area = max(max_area, area)
        if height[left] < height[right]:
            left += 1
        else:
            right -= 1
        # 提前终止判断
        if max_area >= max_h * (right - left):
            break
    return max_area

优化点2：跳过无效移动

移动指针时，可以跳过那些比当前边界更矮的线。

def maxArea_skip(height):
    left, right = 0, len(height) - 1
    max_area = 0
    while left < right:
        h = min(height[left], height[right])
        max_area = max(max_area, h * (right - left))
        # 跳过更矮的线
        while left < right and height[left] <= h:
            left += 1
        while left < right and height[right] <= h:
            right -= 1
    return max_area

边界条件处理

特殊情况

1. 空数组或单元素数组：返回0
2. 所有高度相同：面积为 height[0] * (n-1)
3. 存在零高度：不影响计算（min操作会自动处理）

防御性编程

def maxArea_defensive(height):
    if not height or len(height) < 2:
        return 0
    # 其余逻辑与之前相同
    ...

测试用例设计

基础测试

assert maxArea([1,1]) == 1
assert maxArea([4,3,2,1,4]) == 16
assert maxArea([1,2,1]) == 2

极端情况

assert maxArea([]) == 0
assert maxArea([10000] * 10000) == 10000 * 9999
assert maxArea([0,0,0,0]) == 0

性能测试

import random
large_input = [random.randint(0, 10000) for _ in range(100000)]
# 应能在1秒内完成

不同语言实现

Java实现

public int maxArea(int[] height) {
    int left = 0, right = height.length - 1;
    int maxArea = 0;
    while (left < right) {
        int area = Math.min(height[left], height[right]) * (right - left);
        maxArea = Math.max(maxArea, area);
        if (height[left] < height[right]) {
            left++;
        } else {
            right--;
        }
    }
    return maxArea;
}

C++实现

int maxArea(vector<int>& height) {
    int left = 0, right = height.size() - 1;
    int max_area = 0;
    while (left < right) {
        max_area = max(max_area, min(height[left], height[right]) * (right - left));
        if (height[left] < height[right]) {
            left++;
        } else {
            right--;
        }
    }
    return max_area;
}

实际应用场景

1. 资源分配问题：如分配服务器资源时寻找最优配置
2. 物理建模：计算实际容器的最大容量
3. 金融分析：寻找股票买卖的最佳时机（类似问题）
4. 图像处理：寻找图像中的最大矩形区域

相关算法扩展

接雨水问题

一个更复杂的变种问题，需要计算所有凹陷处能接的雨水量。

def trap(height):
    left, right = 0, len(height) - 1
    left_max = right_max = 0
    result = 0
    while left < right:
        if height[left] < height[right]:
            if height[left] >= left_max:
                left_max = height[left]
            else:
                result += left_max - height[left]
            left += 1
        else:
            if height[right] >= right_max:
                right_max = height[right]
            else:
                result += right_max - height[right]
            right -= 1
    return result

最大矩形面积

在直方图中寻找最大矩形面积，需要使用单调栈解决。

常见错误分析

1. 错误理解题意：认为要找最高的两条线（实际是面积最大）
2. 指针移动错误：同时移动两个指针会错过最优解
3. 边界处理不当：忽略数组长度小于2的情况
4. 计算错误：宽度计算时使用错误的索引差值

性能对比

方法	时间复杂度	空间复杂度	实际运行时间(1e5数据)
暴力法	O(n²)	O(1)	>10s
双指针法	O(n)	O(1)	~0.01s
优化双指针法	O(n)	O(1)	~0.008s

总结

1. 双指针法是解决此类问题的黄金法则：通过有策略地移动指针，将时间复杂度从O(n²)降到O(n)
2. 理解问题本质是关键：盛水量由宽度和最小高度共同决定
3. 优化需要基于正确性：所有优化都应建立在保证算法正确性的基础上
4. 多语言实现有助于深入理解：不同语言的实现可以加深对算法核心逻辑的理解

练习题

1. 修改算法，返回最大面积对应的两个索引位置
2. 实现一个可视化函数，绘制数组和最大容器的示意图
3. 研究当高度可能为负数时的处理方案
4. 将问题扩展到三维空间（寻找三个边界形成的最大容器）

---

本文详细介绍了盛最多水容器问题的多种解决方案，从暴力法到最优的双指针法，并提供了多个优化版本和不同语言实现。通过理解这个问题的解决过程，可以掌握双指针类问题的通用解法思路。 “`