224 lines
7.6 KiB
Markdown
224 lines
7.6 KiB
Markdown
---
|
||
tags: ["LeetCode", "双指针", "中等"]
|
||
create time: 2026-05-13 16:00
|
||
---
|
||
|
||
# 05-盛最多水的容器
|
||
|
||
## 题面
|
||
|
||
给定一个长度为 `n` 的整数数组 `height` 。有 `n` 条垂线，第 `i` 条线的两个端点是 `(i, 0)` 和 `(i, height[i])` 。
|
||
|
||
找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。
|
||
|
||
返回容器可以储存的最大水量。**说明：你不能倾斜容器。**
|
||
|
||
**示例 1：**
|
||
|
||
```
|
||
输入：height = [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
|
||
```
|
||
|
||
**提示：**
|
||
|
||
- `n == height.length`
|
||
- `2 <= n <= 10^5`
|
||
- `0 <= height[i] <= 10^4`
|
||
|
||
---
|
||
|
||
## 思路
|
||
|
||
> [!question] 💡 思考
|
||
> 容器的蓄水量由什么决定？直观上，越高的墙能装越多水，两根墙的间距越大也能装越多水。但这是一个"木桶效应"——实际容量取决于**较矮的那根墙**。用数学式表达：对于第 i 和第 j 两根墙（i < j），容量为 `min(height[i], height[j]) * (j - i)`。
|
||
|
||
### 方法一：暴力枚举 ❌
|
||
|
||
最直接的思路是枚举所有可能的两两组合：
|
||
|
||
```
|
||
maxArea = 0
|
||
for i 从 0 到 n-1:
|
||
for j 从 i+1 到 n-1:
|
||
area = min(height[i], height[j]) * (j - i)
|
||
maxArea = max(maxArea, area)
|
||
```
|
||
|
||
- **时间复杂度：O(n²)** — 需要检查 C(n,2) 对组合
|
||
- **空间复杂度：O(1)**
|
||
|
||
但在 `n ≤ 10^5` 的约束下，O(n²) 必然超时，必须寻找更优解法。
|
||
|
||
### 方法二：双指针（最优 ⭐）
|
||
|
||
> [!info] 🎯 核心思想
|
||
> 设左指针 `left = 0`、右指针 `right = n - 1`，指向两端。每次计算当前面积后，**将较短的那根墙的指针向内移动一格**。重复直到两指针相遇。
|
||
|
||
这个策略看似贪心，却能保证找到全局最优解。关键在于以下推理：
|
||
|
||
> [!abstract] 🔬 正确性证明
|
||
>
|
||
> 假设当前 `left` 指向短边（即 `height[left] < height[right]`）。我们考虑以 `left` 为左边界的所有容器：
|
||
>
|
||
> - 它们的高度上限是 `height[left]`
|
||
> - 它们的宽度上限是当前 `right - left`（即右指针还在最远端时）
|
||
>
|
||
> 如果把右指针向内移，新的宽度更小、高度上限仍是 `height[left]`，面积只会缩小 → **所以以 `left` 为左边界时，已经和当前最远的右指针组成的面积就是它的最优可能。**
|
||
>
|
||
> 因此可以放心地把 `left` 向内移动——我们不会错过更优解。
|
||
>
|
||
> 对称地，如果 `height[left] >= height[right]`，则把 `right` 向内移动。
|
||
|
||
```mermaid
|
||
flowchart LR
|
||
A["开始\nleft = 0, right = n-1"] --> B{"left < right?"}
|
||
B -->|"否"| G["返回 maxArea"]
|
||
B -->|"是"| H["area = min(h[left], h[right]) * (right-left)"]
|
||
H --> I["maxArea = max(maxArea, area)"]
|
||
I --> J{"h[left] < h[right]?"}
|
||
J -->|"是"| K["left++"]
|
||
J -->|"否"| L["right--"]
|
||
K --> B
|
||
L --> B
|
||
```
|
||
|
||
以 `height = [1, 8, 6, 2, 5, 4, 8, 3, 7]` 为例：
|
||
|
||
> [!abstract] 🔍 逐步推演
|
||
> 注意每步的面积计算公式：**宽度 = right - left，高度 = min(h[left], h[right])**。
|
||
|
||
| 步骤 | left | right | h[left] | h[right] | 容量计算 | maxArea | 动作 |
|
||
|------|------|-------|---------|----------|----------|---------|------|
|
||
| 初始 | 0 | 8 | 1 | 7 | min(1,7) × 8 = **8** | 8 | left++（左边更矮） |
|
||
| 1 | 1 | 8 | 8 | 7 | min(8,7) × 7 = **49** | 49 | right--（右边更矮） |
|
||
| 2 | 1 | 7 | 8 | 3 | min(8,3) × 6 = 18 | 49 | right-- |
|
||
| 3 | 1 | 6 | 8 | 8 | min(8,8) × 5 = 40 | 49 | right--（相等，任意移动一边） |
|
||
| 4 | 1 | 5 | 8 | 4 | min(8,4) × 4 = 16 | 49 | right-- |
|
||
| 5 | 1 | 4 | 8 | 5 | min(8,5) × 3 = 15 | 49 | right-- |
|
||
| 6 | 1 | 3 | 8 | 2 | min(8,2) × 2 = 4 | 49 | right-- |
|
||
| 7 | 1 | 2 | 8 | 6 | min(8,6) × 1 = 6 | 49 | right-- |
|
||
| 结束 | 2 | 2 | — | — | — | **49** | 相遇退出 |
|
||
|
||
最佳方案对应 **步骤 1**：左边界索引 1（高度 8）与右边界索引 8（高度 7），面积 = min(8, 7) × 7 = **49**。
|
||
|
||
- **时间复杂度：O(n)** — 双指针各移动 n-1 次就相遇，总共 O(n) 步
|
||
- **空间复杂度：O(1)** — 仅使用常数个变量
|
||
|
||
---
|
||
|
||
## 代码提示
|
||
|
||
```
|
||
// 伪代码模板
|
||
left = 0
|
||
right = n - 1
|
||
maxArea = 0
|
||
|
||
while left < right:
|
||
// 计算当前容器面积
|
||
width = right - left
|
||
minHeight = min(height[left], height[right])
|
||
area = width * minHeight
|
||
maxArea = max(maxArea, area)
|
||
|
||
// 移动较矮的一边的指针
|
||
if height[left] < height[right]:
|
||
left++
|
||
else:
|
||
right--
|
||
|
||
return maxArea
|
||
```
|
||
|
||
Go 语言中可以用 `min` / `max` 内置函数简化代码（Go 1.21+ 支持泛型版本的 `min` 和 `max`）。
|
||
|
||
```go
|
||
// Go 风格精简版骨架
|
||
maxArea := 0
|
||
for left, right := 0, len(height)-1; left < right; {
|
||
w := right - left
|
||
h := min(height[left], height[right])
|
||
if area := w * h; area > maxArea {
|
||
maxArea = area
|
||
}
|
||
if height[left] < height[right] {
|
||
left++
|
||
} else {
|
||
right--
|
||
}
|
||
}
|
||
return maxArea
|
||
```
|
||
|
||
---
|
||
|
||
## 技巧
|
||
|
||
> [!tip] 🔑 核心模式：收缩边界（Contraction Boundaries）
|
||
> 本题的双指针不是"同向追赶"（如滑动窗口），而是**相向收缩**。这类模式适用于"在有序或对称的空间中逐步缩小搜索范围"的场景。典型特征：① 初始状态定义了最大的搜索空间；② 存在一种单调规则可以安全地剔除不可能的候选解。
|
||
|
||
> [!info] 🔬 为什么不能同时移动两个指针？
|
||
> 当 `height[left] == height[right]` 时，两边都应该移动。因为左右都是同样的短板，任意单边移动后都找不出比当前更大的以其中一个为边界的有效组合。只有两边一起"丢弃"才能避免遗漏以更高内墙构成的更大面积。
|
||
|
||
> [!note] 🐹 Go 中的 min/max
|
||
> Go 1.21+ 提供了类型推导的内置 `min` 和 `max` 函数，可以直接用于 `int` 类型：`min(a, b)` / `max(a, b)`。如果使用旧版本 Go，需自行实现：
|
||
> ```go
|
||
> func min(a, b int) int {
|
||
> if a < b { return a }
|
||
> return b
|
||
> }
|
||
> ```
|
||
|
||
> [!danger] ⚠️ 常见陷阱
|
||
> 有些同学会想：既然要找最大面积，能不能直接找最高的那根墙作为一端？这样想的漏洞在于，另一端的墙也要够高才行。最高墙可能在中间，它的两侧都没有足够高的匹配，形成的面积未必最优。必须像双指针那样"系统性地扫描"。
|
||
|
||
> [!summary] 📊 两种双指针对比
|
||
> | 模式 | 指针运动 | 典型问题 | 本题适用性 |
|
||
> |------|----------|----------|------------|
|
||
> | 快慢指针 | 同向，速度不同 | 移动零、移除元素 | ✅ 部分场景 |
|
||
> | 相向收缩 | 各自向内 | 盛水容器、两数之和 II | ✅ 本题采用 |
|
||
|
||
---
|
||
|
||
## 代码
|
||
|
||
```go
|
||
func maxArea(height []int) int {
|
||
maxArea := 0
|
||
left, right := 0, len(height)-1
|
||
|
||
for left < right {
|
||
// 计算当前容器的水量
|
||
width := right - left
|
||
h := min(height[left], height[right])
|
||
area := width * h
|
||
if area > maxArea {
|
||
maxArea = area
|
||
}
|
||
|
||
// 移动较短边的指针：淘汰"短板"
|
||
if height[left] < height[right] {
|
||
left++
|
||
} else {
|
||
right--
|
||
}
|
||
}
|
||
|
||
return maxArea
|
||
}
|
||
```
|
||
|
||
> [!success] ✅ 运行验证
|
||
> - **LeetCode 第 11 题**，通过率约 62%，经典的中档算法题。
|
||
> - 核心洞察："淘汰短板"的贪心策略可以通过反证法严格证明 —— 被跳过的那些组合不可能产生更大的面积。
|
||
> - 这道题也是理解"什么时候贪心是安全的"的最佳练习题之一。当且仅当被淘汰的方案能被证明**一定劣于已保留方案**时，贪心才是正确的。本题中，由于宽度和高度都只减不增，淘汰短边的决策是安全的。
|