11. 盛最多水的容器 (Medium)
专题归类： 02-双指针与滑动窗口 · 04-贪心 LeetCode 链接： https://leetcode.cn/problems/container-with-most-water/
在线做题： 写 Python 代码并运行 · Java 跳转 LeetCode
题目描述
给定一个长度为 n 的整数数组 height。有 n 条垂线，第 i 条线的两个端点是 (i, 0) 和 (i, height[i])。
找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。
返回容器可以储存的最大水量。
说明： 你不能倾斜容器。
示例：
输入：height = [1, 8, 6, 2, 5, 4, 8, 3, 7]
输出：49
解释：图中垂直线高度为 8 和 7（索引 1 和 8），
容器宽度为 7，高度为 min(8, 7) = 7，
面积 = 7 × 7 = 49
补充说明：
- 数组长度范围：
2 <= n <= 10^5 - 高度范围：
0 <= height[i] <= 10^4
题目详细分析
数据范围含义：
- n 最大 10^5，O(n^2) 的暴力枚举会达到 10^10 次操作，绝对超时。需要 O(n) 或 O(n log n) 的解法。
- height[i] >= 0，但为 0 的柱子无法盛水（高度为 0），可以作为优化的依据。
核心约束：
- 盛水量 = 宽度 × 较矮柱子的高度。这个公式是整个问题的数学基础。
- 宽度 = 两根柱子下标的差值（
right - left）。 - 高度 = 两根柱子高度的最小值（木桶效应——水位取决于较短的木板）。
- 不能倾斜容器——意味着必须严格按照 min(height[left], height[right]) 计算高度。
边界条件：
- 最少 2 根柱子，保证至少有一个容器。
隐藏条件：
- 暴力法不可行，必须找到某种能够”剪枝”或”跳过”的规律。
- 问题的关键洞察在于指针移动策略——移动较高的柱子为什么不会增加面积？
小白版直白理解
想象你有一排高低不同的木板立在河边，你要选两块木板当”墙壁”，和河底围成一个长方形水池。你想让水池装的水最多。
水池装多少水取决于两个因素：
- 两块木板之间的距离（越远越好）
- 较矮的那块木板的高度（水不能漫过矮板）
笨办法： 把所有可能的木板组合都试一遍，算面积。n 块木板有大约 n²/2 种组合，太多了。
聪明办法（对撞指针）： 你从最远的两块木板开始——最左和最右。算完面积后，你把较矮的那块木板往中间挪一格，因为：
- 如果你移动较高的那块，距离变近了，但高度不可能变（因为高度由矮的那块决定），面积只会变小。
- 如果你移动较矮的那块，虽然距离也变近了，但高度有可能变大（下一块木板可能更高），面积还有可能增加。
这样你每次只移动矮的那块，一轮下来就能找到最大值，不用试所有组合！
解题思路
思路一：对撞指针（推荐）
关键洞察： 面积取决于两个因素：宽度和较矮柱子的高度。当两个指针从两端向中间移动时，宽度在持续减小。想要面积变大，唯一的可能是高度增加。
核心推理：
- 假设
height[left] < height[right]（左边较矮）。 - 如果移动
right（较高的），新面积 =(right - left - 1) × min(height[left], height[right-1])。- 宽度减小了 1。
- 由于
height[left]没变，而右边高度无论怎么变，min的值 ≤height[left]。 - 所以新面积 ≤ 旧面积 → 移动较高的指针，面积不可能变大。
- 如果移动
left（较矮的），虽然宽度也减小了，但新的height[left+1]可能比原来的height[left]高，min值有可能变大。
因此，每次都移动较矮的那根柱子是唯一可能增加面积的策略。
def maxArea(height):
"""
对撞指针法
每次移动高度较小的指针，因为移动高的面积不可能变大
"""
left, right = 0, len(height) - 1
max_water = 0
while left < right:
# 计算当前面积
area = (right - left) * min(height[left], height[right])
max_water = max(max_water, area)
# 移动较矮的柱子
if height[left] < height[right]:
left += 1
else:
right -= 1
return max_water思路二：暴力法（不推荐，用于对比）
双重循环遍历所有组合，O(n^2)。当 n 较大时超时。
def maxArea_brute_force(height):
"""暴力法，O(n^2)，会超时"""
n = len(height)
max_water = 0
for i in range(n):
for j in range(i + 1, n):
area = (j - i) * min(height[i], height[j])
max_water = max(max_water, area)
return max_water易错点
- 移动策略搞反： 最容易犯的错误是”移动较高的指针”，这会导致错过最优解。关键推理：移动较高的指针面积不可能变大，所以永远只移动较矮的。
- 高度相等时：
height[left] == height[right]时，移动任意一边都可以。因为两边一样高，无论移动哪边，高度都不可能超过当前值（因为 min 值已经是当前高度了）。习惯上移动left或right都可以。 - 面积计算公式： 面积 =
(right - left) * min(height[left], height[right])，不是max，也不是(right - left + 1)。 - 指针移动方向： 从两端向中间移动（对撞指针），不是同向移动（快慢指针）。这是双指针的两种不同模式。
- 更新最大值的位置： 每次移动指针之前（或之后立即）计算面积并更新最大值，不要只在移动后才计算。
框架提炼
对撞指针模板：
核心模式：两个指针从数组两端向中间移动，每次根据条件移动其中一个指针，逐步缩小搜索范围。
def two_pointers_collision(arr):
"""
对撞指针通用模板
从两端向中间移动，每次移动其中一侧的指针
"""
left, right = 0, len(arr) - 1
result = 0 # 或初始化为极小值/极大值
while left < right:
# 1. 根据当前状态计算候选结果
candidate = compute(arr, left, right)
result = max(result, candidate) # 或 min
# 2. 决定移动哪一侧
if should_move_left(arr, left, right):
left += 1
else:
right -= 1
return result对撞指针 vs 快慢指针：
| 类型 | 移动方式 | 典型应用 |
|---|---|---|
| 对撞指针 | 从两端向中间 | 盛水最多容器、接雨水、两数之和(有序) |
| 快慢指针 | 同向移动，一快一慢 | 移动零、移除元素、链表找环 |