【LeetCode】11.盛最多水的容器

📚 题目概要

给定一个整数数组 height，每个元素表示垂直线的长度。找出两条垂直线，使其与 x 轴构成的容器能容纳最多的水，返回最大水量（即面积）。

🧰 前置知识

• 双指针技巧：通过左右指针向中间移动缩小搜索范围。
• 贪心思想：每一步选择局部最优解（移动较矮的指针），以逼近全局最优解。

🚧 问题难点

1. 高效搜索：暴力法时间复杂度为 O(n²)，需优化至 O(n)。
2. 高度与宽度的权衡：面积由较矮的高度和宽度共同决定，需动态调整指针以平衡两者。

🔑 关键思路

1. 双指针初始化：左指针从数组头部开始，右指针从尾部开始。
2. 移动策略：每次移动较矮的指针，以尝试找到更高的高度。
3. 实时更新最大值：在每次移动后计算当前面积，并记录历史最大值。

💻 代码实现

def maxArea(self, height: List[int]) -> int:
    left, right = 0, len(height) - 1  # 初始化双指针
    max_water = 0
    
    while left < right:
        # 计算当前容器的水量
        current_height = min(height[left], height[right])
        current_width = right - left
        current_water = current_height * current_width
        
        # 更新最大水量
        if current_water > max_water:
            max_water = current_water
        
        # 移动较矮的指针以寻求更高高度
        if height[left] < height[right]:
            left += 1
        else:
            right -= 1
    
    return max_water

代码注释

• 第2行：初始化双指针，左指针在数组头，右指针在数组尾。
• 第6-8行：计算当前容器的水量（高度取两指针中的较小值，宽度为指针间距）。
• 第11-12行：动态更新历史最大水量。
• 第15-18行：移动较矮的指针，尝试找到更高的高度。

📊 复杂度分析

• 时间复杂度：O(n)，双指针最多遍历所有元素一次。
• 空间复杂度：O(1)，仅需常数级额外空间。

❗ 易错点与测试案例

易错点

1. 误移动较高指针：若错误移动较高的指针，可能错过更大面积的机会。
2. 未及时更新最大值：漏掉中间状态的面积计算。

测试案例

• 案例1：
  输入：height = [1,8,6,2,5,4,8,3,7]
  输出：49
  解释：选择第2条线（高度8）和第9条线（高度7），宽度为7，面积8×7=56 → 实际为7×7=49（正确计算方式）。

• 案例2：
  输入：height = [1,1]
  输出：1
  解释：两条线高度均为1，宽度为1，面积1×1=1。

🔗 总结与扩展

模式归纳

• 双指针夹逼法：适用于有序或可通过局部决策缩小范围的场景。
• 同类问题：
  • 接雨水问题：计算凹槽能接的雨水量。
  • 三数之和：通过双指针减少搜索空间。

核心思维

• 贪心选择：通过局部最优（移动较矮指针）逐步逼近全局最优解。
• 平衡取舍：在高度和宽度之间动态调整，确保每次移动能保留潜在的最大面积可能。