LeetCode 11 盛最多水的容器：双指针 O(n) 题解与多语言实现

• 示例工程

本文围绕 LeetCode 11. 盛最多水的容器 展开，完整讲解题目定义、从 $O(n^2)$ 暴力枚举到双指针 $O(n)$ 贪心策略的推导过程、正确性证明，并给出 Python3、Java、C++、Go、Rust 等 9 种语言的完整实现。读完本文，你能掌握“面积类容器问题”中“移动较短板”这一经典贪心思想的论证方式，并能直接复用仓库中的多语言代码。

![盛最多水的容器题目示意图：垂直线代表数组 [1,8,6,2,5,4,8,3,7]，蓝色部分为容器可容纳的水](solution/0000-0099/0011.Container With Most Water/images/question_11.jpg)

题目描述

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

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

说明：你不能倾斜容器。

示例 1：

输入：[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 \le n \le 10^5$
• $0 \le height[i] \le 10^4$

方法一：暴力枚举（无法通过）

最直接的思路是枚举所有下标对 $(i, j)$，其中 $0 \le i < j < n$。对于每一对下标，容器面积为：

$$S(i, j) = \min(height[i], height[j]) \times (j - i)$$

即“较短的边决定高度，两条线的水平距离决定宽度”。暴力枚举的总复杂度为 $O(n^2)$。由题面约束 $n \le 10^5$，$n^2$ 可达 $10^{10}$ 量级，无法通过，因此必须寻找更优策略。

方法二：双指针贪心

这是本题的标准解法，也是整个题解的核心。

算法思路

使用两个指针 $l$ 和 $r$ 分别指向数组的左右两端，即 $l = 0$，$r = n - 1$，其中 $n$ 是数组的长度。

使用变量 $ans$ 记录容器的最大容量，初始化为 $0$。进入循环，每次循环中：

1. 计算当前容器的容量 $t = \min(height[l], height[r]) \times (r - l)$，并将 $ans$ 更新为 $\max(ans, t)$；
2. 比较 $height[l]$ 与 $height[r]$ 的大小：若 $height[l] < height[r]$，则移动 $l$ 指针（$l \leftarrow l + 1$）；否则移动 $r$ 指针（$r \leftarrow r - 1$）；
3. 重复直到 $l \ge r$，返回 $ans$。

为什么每次移动较矮的一侧

关键观察：容器的高度永远由较短的那根线决定。

假设当前区间 $[l, r]$ 中 $height[l] < height[r]$，即左端是短板。此时若向内移动较高的一端（$r$），区间宽度 $(r - l)$ 必然减小，而新容器的高度仍然受 $height[l]$ 限制（不会超过原来的较短板高度），所以面积必然不增反降。因此移动 $r$ 没有任何收益，唯一值得尝试的是移动 $l$——只有让短板一侧“碰到”更高的线，才可能形成更大的面积。

这一贪心策略的正确性可以从反证角度理解：对于短板一侧的当前下标 $l$，它与区间内任意其他下标 $j$（$l < j < r$）组成的容器，其高度上界为 $\min(height[l], height[j]) \le height[l]$，宽度 $(j - l) < (r - l)$，面积严格小于当前 $[l, r]$ 的面积。也就是说，以当前短板 $l$ 为边的所有“未探索”容器都不可能优于当前已记录的面积，因此可以安全地舍弃 $l$，将指针向内收缩。由于每一步必然移动一个指针，每个下标至多被访问一次，指针相遇时算法终止。

复杂度分析

• 时间复杂度：$O(n)$，其中 $n$ 是数组height的长度。每轮循环至少移动一个指针，最多执行 $n - 1$ 轮。
• 空间复杂度：$O(1)$，只使用了 $l$、$r$、$ans$ 等常数额外空间。

多语言实现

仓库中该题目的完整实现位于 solution/0000-0099/0011.Container With Most Water/ 目录，与 README.md 中给出的代码一一对应，覆盖 Python3、Java、C++、Go、TypeScript、Rust、JavaScript、C#、PHP、C 共 10 种语言。以下摘取几个代表性实现。

Python3

见 Solution.py：

class Solution: def maxArea(self, height: List[int]) -> int: l, r = 0, len(height) - 1 ans = 0 while l < r: t = min(height[l], height[r]) * (r - l) ans = max(ans, t) if height[l] < height[r]: l += 1 else: r -= 1 return ans

Java

见 Solution.java：

class Solution { public int maxArea(int[] height) { int l = 0, r = height.length - 1; int ans = 0; while (l < r) { int t = Math.min(height[l], height[r]) * (r - l); ans = Math.max(ans, t); if (height[l] < height[r]) { ++l; } else { --r; } } return ans; } }

C++

见 Solution.cpp：

class Solution { public: int maxArea(vector<int>& height) { int l = 0, r = height.size() - 1; int ans = 0; while (l < r) { int t = min(height[l], height[r]) * (r - l); ans = max(ans, t); if (height[l] < height[r]) { ++l; } else { --r; } } return ans; } };

Go

见 Solution.go。Go 版本利用了命名返回值(ans int)，省去显式声明：

func maxArea(height []int) (ans int) { l, r := 0, len(height)-1 for l < r { t := min(height[l], height[r]) * (r - l) ans = max(ans, t) if height[l] < height[r] { l++ } else { r-- } } return }

Rust

见 Solution.rs。这里可以看到一个与 C++ 实现细节的差异：索引差r - l是usize类型，需要显式转换为i32才能与高度相乘：

impl Solution { pub fn max_area(height: Vec<i32>) -> i32 { let mut l = 0; let mut r = height.len() - 1; let mut ans = 0; while l < r { ans = ans.max(height[l].min(height[r]) * ((r - l) as i32)); if height[l] < height[r] { l += 1; } else { r -= 1; } } ans } }

C

C 语言没有内置min/max函数，Solution.c 自行实现了对应的工具函数，且函数签名遵循 LeetCode 的“指针 + 长度”传参约定：

int min(int a, int b) { return a < b ? a : b; } int max(int a, int b) { return a > b ? a : b; } int maxArea(int* height, int heightSize) { int l = 0, r = heightSize - 1; int ans = 0; while (l < r) { int t = min(height[l], height[r]) * (r - l); ans = max(ans, t); if (height[l] < height[r]) { ++l; } else { --r; } } return ans; }

其余语言的实现可参考 Solution.ts（TypeScript）、Solution.js（JavaScript）、Solution.cs（C#）和 Solution.php（PHP），逻辑与上述实现完全一致；英文题解见 README_EN.md。

小结

• 问题本质：在 $O(n^2)$ 对下标中寻找使 $\min(height[i], height[j]) \times (j - i)$ 最大的组合，$n \le 10^5$ 决定暴力法不可行。
• 核心策略：左右双指针从最宽区间出发，每轮记录当前面积后移动较矮的一侧；由于短板一侧的当前下标与区间内其余下标组成的面积必然更差，该剪枝是安全的。
• 复杂度：时间 $O(n)$、空间 $O(1)$，且各语言实现结构高度一致，便于对照阅读与移植。

• 示例工程