#盛最多水的容器

#题目描述

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

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

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

说明：你不能倾斜容器。

#思路分析

这道题的核心在于理解：容器的盛水量由两个因素决定：

1. 宽度：两条线之间的距离 right - left
2. 高度：两条线中较短的那条 Math.min(height[left], height[right])

面积 = 宽度 × 高度，我们的目标是找到使这个乘积最大的两条线。

#为什么使用双指针？

暴力解法需要枚举所有可能的线对，时间复杂度为 O(n²)。而双指针法可以将其优化到 O(n)。

双指针的贪心策略：

1. 初始状态：左指针指向最左端，右指针指向最右端，此时宽度最大。
2. 移动策略：每次移动较短的一侧指针。

#为什么要移动较短的一侧？

这是算法的关键思想，需要通过反证法理解：

假设当前 height[left] < height[right]，即左侧较短：

• 如果移动右指针：

  • 宽度一定减小（right-- 使距离变小）
  • 高度由短板决定，仍然 ≤ height[left]（因为短板没变或变得更短）
  • 因此面积一定不会变大，不可能找到更优解

• 如果移动左指针：

  • 宽度减小
  • 但高度有可能增大（如果新的 height[left+1] 更高）
  • 面积有可能变大，存在找到更优解的机会

因此，移动较短的一侧才有可能获得更大的面积。这是一个贪心策略：每次排除那些不可能产生更优解的情况。

#算法步骤

1. 初始化左指针 left = 0，右指针 right = height.length - 1
2. 初始化最大面积 maxArea = 0
3. 当 left < right 时循环：
   • 计算当前面积：area = Math.min(height[left], height[right]) × (right - left)
   • 更新最大面积：maxArea = Math.max(maxArea, area)
   • 移动较短的一侧指针：
     • 若 height[left] < height[right]，则 left++
     • 否则 right--
4. 返回 maxArea

#示例代码

/**
 * 使用双指针法计算容器能盛的最大水量
 * 
 * 算法思路：
 * 1. 使用两个指针分别从数组两端向中间移动
 * 2. 每次计算当前指针位置能形成的容器面积
 * 3. 移动较短的那一侧指针，因为短板决定了容器高度
 * 4. 持续更新并记录最大面积
 * 
 * 时间复杂度：O(n) - 每个元素最多被访问一次
 * 空间复杂度：O(1) - 只使用常量额外空间
 * 
 * @param height - 整数数组，每个元素代表一条垂直线的高度
 * @returns 返回容器能盛的最大水量（面积）
 * 
 * @example
 * maxArea([1, 8, 6, 2, 5, 4, 8, 3, 7]) // 返回 49
 */
export function maxArea(height: number[]): number {
    // 初始化左指针，指向数组起始位置
    let left = 0;
    // 初始化右指针，指向数组末尾位置
    let right = height.length - 1;
    // 用于记录遍历过程中遇到的最大面积
    let maxArea = 0;

    // 当左右指针还未相遇时，继续循环
    while (left < right) {
        // 计算当前两个指针之间的宽度（水平距离）
        const width = right - left;
        
        // 计算当前容器的高度（取两边较短的一边，因为短板决定了水位）
        const currentHeight = Math.min(height[left], height[right]);

        // 计算当前容器的面积 = 宽度 × 高度
        const area = currentHeight * width;
        
        // 更新最大面积：如果当前面积更大，则更新
        maxArea = Math.max(maxArea, area);

        // 移动指针策略：移动较短的一侧
        // 原因：如果移动较高的一侧，新的高度只可能不变或变小，而宽度一定变小
        // 因此移动较短的一侧才有可能找到更大的面积
        if (height[left] < height[right]) {
            // 左侧较短，向右移动左指针
            left++;
        } else {
            // 右侧较短或两侧相等，向左移动右指针
            right--;
        }
    }
    
    // 返回找到的最大面积
    return maxArea;
}

#复杂度分析

• 时间复杂度：O(n)，其中 n 是数组长度。双指针从两端向中间移动，每个元素最多被访问一次。
• 空间复杂度：O(1)，只使用了常量级别的额外空间。

#示例演示

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

初始状态

索引:  0  1  2  3  4  5  6  7  8
高度:  1  8  6  2  5  4  8  3  7
      ↑                       ↑
     left                   right

逐步演示

结束：left >= right，循环结束，返回最大面积 49。

这个最大面积是由索引 1（高度 8）和索引 8（高度 7）形成的容器产生的。

#关键要点

1. 短板效应：容器的高度由较短的一侧决定，这是木桶原理的应用。
2. 贪心策略：移动较短的一侧才可能找到更大的面积，移动较高的一侧永远不会产生更优解。
3. 空间换时间的反面：这道题通过巧妙的指针移动策略，避免了暴力枚举，在 O(1) 空间内实现了 O(n) 的时间复杂度。