问题描述：

给定一个长度为 n 的整数数组 height 。有 n 条垂线，第 i 条线的两个端点是 ( i , 0 ) 和

( i , height [ i ] ) 。

找出其中的两条线，使得它们与 X 轴共同构成的容器可以容纳最多的水。

返回容器可以储存的最大水量。

说明：你不能倾斜容器。

示例1：

输入：[ 1,8,6,2,5,4,8,3,7 ]

输出：49

解释：图中垂直线代表输入数组 [1,8,6,2,5,4,8,3,7]。在此情况下，容器能够容纳水（表示为蓝色部分）的最大值为 49。

示例2：

输入：height = [1,1]

输出：1

解决方法：

方法一：暴力枚举

class Solution {
public:
    int maxArea(vector<int>& height) {
        int maxlength = 0;
        int n = height.size();
        int len = 0;
        for(int i = 0;i < n-1;i++)
        {
            for(int j =i+1;j < n;j++)
            {
                len = (j-i)*min(height[i],height[j]);
                if(len > maxlength){
                    maxlength = len;
                }
            }
        }
        return maxlength;
    }
};

算法思路：

• 两层 for 循环遍历所有可能的容器组合 （i，j）；
• 对于每对组合，计算面积：( j - i) * min ( height [ i ] , height [ j ] )；
• 记录遇到的最大面积；
• 对于大部分测试用例可以通过，个别运行超时，需要优化。

复杂度分析：

• 时间复杂度：O(n²)   需要检查所有可能的组合
• 空间复杂度：O(1)    只使用常数空间

方法二：双指针法

class Solution:
    def maxArea(self, height: List[int]) -> int:
        left = 0
        right = len(height) - 1
        maxarea = 0
        while left < right:
            curarea = min(height[left], height[right]) * (right - left)
            maxarea = max(maxarea, curarea)
            if height[left] < height[right]:
                left += 1
            else:
                right -= 1
        return maxarea

算法思路：

• 初始化两个指针： left指向数组开头，right指向数组的末尾；
• 计算当前容器的面积并更新最大值；
• 移动高度较小的指针，因为指针的移动导致宽度减少，只有移动小的指针才可能出现大面积。

复杂度分析：

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

问题详解：

双指针的正确性：容器的面积由两个因素决定：宽度（两个指针之间的距离），高度（两个边界中较矮的那个）

移动策略合理性：

• 当我们移动指针时，宽度必然减小；

• 为了可能获得更大的面积，我们需要寻找更高的边界；

• 移动较短的边界有可能找到更高的边界，从而弥补宽度减少的损失；

• 移动较长的边界只会让面积保持不变或减小。

示例：以 height = [1,8,6,2,5,4,8,3,7] 为例

步骤1: left=0(高1), right=8(高7), 面积=8（1*8） 步骤2: 移动left -> left=1(高8), right=8(高7), 面积=49 （7*7） 步骤3: 移动right -> left=1(高8), right=7(高3), 面积=18 （6*3） 步骤4: 移动right -> left=1(高8), right=6(高8), 面积=40 （5*8） ... 最终最大面积：49

总结：

1. 暴力法 思路简单直接，但时间复杂度高，不适合处理大规模数据；

2. 双指针法 是这个问题的最优解，通过指针移动策略将时间复杂度从 O(n²) 优化到 O(n)；

3. 核心思想：总是移动较短的边界，因为只有这样才能可能找到更高的边界来弥补宽度减少的损失；

4. 适用场景：这种双指针技巧在解决数组相关的最优化问题时非常有用，特别是当问题具有单调性时；