【LeetCode】11.盛最多水的容器
📚 题目概要
给定一个整数数组 height，每个元素表示垂直线的长度。找出两条垂直线，使其与 x 轴构成的容器能容纳最多的水，返回最大水量（即面积）。
🧰 前置知识
- 双指针技巧：通过左右指针向中间移动缩小搜索范围。
- 贪心思想：每一步选择局部最优解（移动较矮的指针），以逼近全局最优解。
🚧 问题难点
- 高效搜索：暴力法时间复杂度为 O(n²)，需优化至 O(n)。
- 高度与宽度的权衡：面积由较矮的高度和宽度共同决定，需动态调整指针以平衡两者。
🔑 关键思路
- 双指针初始化：左指针从数组头部开始，右指针从尾部开始。
- 移动策略：每次移动较矮的指针，以尝试找到更高的高度。
- 实时更新最大值：在每次移动后计算当前面积，并记录历史最大值。
💻 代码实现
def maxArea(self, height: List[int]) -> int:left, right = 0, len(height) - 1 # 初始化双指针max_water = 0while left < right:# 计算当前容器的水量current_height = min(height[left], height[right])current_width = right - leftcurrent_water = current_height * current_width# 更新最大水量if current_water > max_water:max_water = current_water# 移动较矮的指针以寻求更高高度if height[left] < height[right]:left += 1else:right -= 1return max_water
代码注释
- 第2行：初始化双指针，左指针在数组头，右指针在数组尾。
- 第6-8行：计算当前容器的水量（高度取两指针中的较小值，宽度为指针间距）。
- 第11-12行：动态更新历史最大水量。
- 第15-18行：移动较矮的指针，尝试找到更高的高度。
📊 复杂度分析
- 时间复杂度：O(n)，双指针最多遍历所有元素一次。
- 空间复杂度：O(1)，仅需常数级额外空间。
❗ 易错点与测试案例
易错点
- 误移动较高指针：若错误移动较高的指针，可能错过更大面积的机会。
- 未及时更新最大值：漏掉中间状态的面积计算。
测试案例
-
案例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。
🔗 总结与扩展
模式归纳
- 双指针夹逼法：适用于有序或可通过局部决策缩小范围的场景。
- 同类问题：
- 接雨水问题：计算凹槽能接的雨水量。
- 三数之和：通过双指针减少搜索空间。
核心思维
- 贪心选择：通过局部最优（移动较矮指针）逐步逼近全局最优解。
- 平衡取舍：在高度和宽度之间动态调整，确保每次移动能保留潜在的最大面积可能。