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

示例工程【免费下载链接】leetcodeLeetCode solutions in any programming language | 多种编程语言实现 LeetCode、《剑指 Offer第 2 版》、《程序员面试金典第 6 版》题解项目地址https://gitcode.com/doocs/leetcode点击查看免费下载本文围绕 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$。进入循环每次循环中计算当前容器的容量 $t \min(height[l], height[r]) \times (r - l)$并将 $ans$ 更新为 $\max(ans, t)$比较 $height[l]$ 与 $height[r]$ 的大小若 $height[l] height[r]$则移动 $l$ 指针$l \leftarrow l 1$否则移动 $r$ 指针$r \leftarrow r - 1$重复直到 $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.pyclass 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 ansJava见 Solution.javaclass 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.cppclass Solution { public: int maxArea(vectorint 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: Veci32) - 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 } }CC 语言没有内置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.tsTypeScript、Solution.jsJavaScript、Solution.csC#和 Solution.phpPHP逻辑与上述实现完全一致英文题解见 README_EN.md。小结问题本质在 $O(n^2)$ 对下标中寻找使 $\min(height[i], height[j]) \times (j - i)$ 最大的组合$n \le 10^5$ 决定暴力法不可行。核心策略左右双指针从最宽区间出发每轮记录当前面积后移动较矮的一侧由于短板一侧的当前下标与区间内其余下标组成的面积必然更差该剪枝是安全的。复杂度时间 $O(n)$、空间 $O(1)$且各语言实现结构高度一致便于对照阅读与移植。赞分享示例工程【免费下载链接】leetcodeLeetCode solutions in any programming language | 多种编程语言实现 LeetCode、《剑指 Offer第 2 版》、《程序员面试金典第 6 版》题解项目地址https://gitcode.com/doocs/leetcode点击查看免费下载相关推荐LeetCode 11. 盛最多水的容器双指针贪心算法全解析多语言实现LeetCode 11. 盛最多水的容器双指针贪心算法全解析多语言实现 本文以 doocs/leetcode 仓库中 0011.Container Wit示例工程LogicStack-LeetCode 题解11. 盛最多水的容器中等——双指针 贪心的正确性证明与 O(n) 实现LogicStack LeetCode 题解11. 盛最多水的容器中等——双指针 贪心的正确性证明与 O n 实现 本文是「刷穿 LeetCode」系教程文档uBlock Origin 免费广告拦截器完整指南从 4 步安装到按站点防火墙控制uBlock Origin 免费广告拦截器完整指南从 4 步安装到按站点防火墙控制 打开一个新闻页横幅、弹窗和一堆看不见的跟踪请求挤在一起页面越刷越卡——网络安全应用安全上一篇Grammarly Premium Cookie自动化采集系统深度解析与架构设计下一篇如何永久保存微信聊天记录WeChatMsg数据留痕完全指南创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考