盛最多水的容器Container With Most Water双指针解法深度解析LeetCode 0011 多语言实现指南【免费下载链接】leetcodeLeetcode solutions项目地址: https://gitcode.com/GitHub_Trending/leetcode1/leetcode本篇文章以 max-water-container.md 解题文档为核心骨架系统讲解 LeetCode 第 11 题「盛最多水的容器」Container With Most Water的两种解法$O(n^2)$ 暴力枚举与 $O(n)$ 双指针。文章完整继承原文档中的算法步骤、全部多语言代码示例与常见陷阱并对照本仓库 python/0011-container-with-most-water.py 等 14 种语言的实际源码进行印证帮助你彻底掌握「双指针」这一高频面试技巧的直觉来源、正确性论证与工程实现细节。题目回顾从两根竖线求最大容器给定一个长度为n的整数数组height其中height[i]表示第i条竖线的高度。选取其中两条线与 x 轴一起构成一个容器容器能够容纳的水量等于area min(height[i], height[j]) * (j - i)即容器高度由较短的那条线决定短板效应宽度是两线之间的水平距离。题目要求返回所有(i, j)组合中能形成的最大面积。说明原文档中函数签名为maxArea(self, heights: List[int])仓库内各语言源码统一使用height命名入参见下方各实现文件二者含义完全相同仅命名风格差异。前置知识在动手解题前建议先确认自己已掌握以下两个基础点原文档 Prerequisites 部分数组Arrays能够通过索引遍历并访问数组元素理解length/size/count等求长方式在不同语言中的差异。双指针技巧Two Pointers从数组两端各放一个指针根据条件向中间收敛用于高效搜索最优配对是本仓库中大量 Two Sum 类题目的通用手段可对照参考 two-integer-sum-ii。解法一暴力枚举Brute Force直觉遍历所有可能的竖线对(i, j)对每一对计算容器面积。容器高度取两条线中较矮者宽度取两者下标之差。由于枚举了全部组合必然能覆盖最大面积对应的那一对因此结果正确代价是需要 $O(n^2)$ 次计算。算法步骤初始化res 0用于追踪已找到的最大面积。使用两层嵌套循环外层循环选定左侧竖线i。内层循环选定右侧竖线j i。对每一对(i, j)高度height min(heights[i], heights[j])宽度width j - i用res max(res, height * width)更新答案。全部组合检查完毕后返回res。多语言实现以下代码完整继承自原文档注意 Go 与部分语言没有内置min函数需自行定义class Solution: def maxArea(self, heights: List[int]) - int: res 0 for i in range(len(heights)): for j in range(i 1, len(heights)): res max(res, min(heights[i], heights[j]) * (j - i)) return respublic class Solution { public int maxArea(int[] heights) { int res 0; for (int i 0; i heights.length; i) { for (int j i 1; j heights.length; j) { res Math.max(res, Math.min(heights[i], heights[j]) * (j - i)); } } return res; } }class Solution { public: int maxArea(vectorint heights) { int res 0; for (int i 0; i heights.size(); i) { for (int j i 1; j heights.size(); j) { res max(res, min(heights[i], heights[j]) * (j - i)); } } return res; } };class Solution { /** * param {number[]} heights * return {number} */ maxArea(heights) { let res 0; for (let i 0; i heights.length; i) { for (let j i 1; j heights.length; j) { res Math.max(res, Math.min(heights[i], heights[j]) * (j - i)); } } return res; } }public class Solution { public int MaxArea(int[] heights) { int res 0; for (int i 0; i heights.Length; i) { for (int j i 1; j heights.Length; j) { res Math.Max(res, Math.Min(heights[i], heights[j]) * (j - i)); } } return res; } }func maxArea(heights []int) int { res : 0 for i : 0; i len(heights); i { for j : i 1; j len(heights); j { area : min(heights[i], heights[j]) * (j - i) if area res { res area } } } return res } func min(a, b int) int { if a b { return a } return b }class Solution { fun maxArea(heights: IntArray): Int { var res 0 for (i in heights.indices) { for (j in i 1 until heights.size) { val area minOf(heights[i], heights[j]) * (j - i) res maxOf(res, area) } } return res } }class Solution { func maxArea(_ heights: [Int]) - Int { var res 0 for i in 0..heights.count { for j in (i 1)..heights.count { res max(res, min(heights[i], heights[j]) * (j - i)) } } return res } }impl Solution { pub fn max_area(heights: Veci32) - i32 { let mut res 0; for i in 0..heights.len() { for j in (i 1)..heights.len() { res res.max(heights[i].min(heights[j]) * (j - i) as i32); } } res } }时间与空间复杂度时间复杂度$O(n ^ 2)$两层循环枚举了所有 $\frac{n(n-1)}{2}$ 个组合。空间复杂度$O(1)$只使用了常数个额外变量。当n达到 $10^5$ 量级时$O(n^2)$ 会超时因此暴力法仅用于验证思路或处理极小规模输入实战中必须使用下面的双指针解法。解法二双指针Two Pointers直觉双指针让我们无需检查每一对组合即可高效搜索最大面积。核心观察如下初始时让左指针l 0、右指针r len(heights) - 1此时容器宽度最大。容器高度被较矮的那条线限制。若要增大面积唯一的希望是移动较矮一侧的指针向内因为移动较矮的线有可能换上一根更高的线从而弥补宽度损失而移动较高的线高度仍被较矮线限制高度不变宽度却必然减小面积只会更小。始终移动较矮的一侧即可系统性地收缩搜索空间覆盖所有可能成为最优的组合。本仓库 hints/max-water-container.md 的 Hint 4 给出了该策略的严谨依据若heights[i]更矮那么任何仍以i为左边界、右边界更靠内的容器宽度更小、高度至多仍为heights[i]面积不可能超过当前这对因此可以安全丢弃较矮的一侧并内移指针heights[j]更矮时同理。算法步骤初始化两个指针l 0r len(heights) - 1。设置res 0存储最大面积。当l r时循环计算当前面积area min(heights[l], heights[r]) * (r - l)用res max(res, area)更新最大面积移动较矮一侧的指针若heights[l] heights[r]则l右移否则r左移。两指针相遇后返回res。多语言实现以下代码完整继承自原文档class Solution: def maxArea(self, heights: List[int]) - int: l, r 0, len(heights) - 1 res 0 while l r: area min(heights[l], heights[r]) * (r - l) res max(res, area) if heights[l] heights[r]: l 1 else: r - 1 return respublic class Solution { public int maxArea(int[] heights) { int l 0; int r heights.length - 1; int res 0; while (l r) { int area Math.min(heights[l], heights[r]) * (r - l); res Math.max(res, area); if (heights[l] heights[r]) { l; } else { r--; } } return res; } }class Solution { public: int maxArea(vectorint heights) { int l 0; int r heights.size() - 1; int res 0; while (l r) { int area min(heights[l], heights[r]) * (r - l); res max(res, area); if (heights[l] heights[r]) { l; } else { r--; } } return res; } };class Solution { /** * param {number[]} heights * return {number} */ maxArea(heights) { let l 0; let r heights.length - 1; let res 0; while (l r) { const area Math.min(heights[l], heights[r]) * (r - l); res Math.max(res, area); if (heights[l] heights[r]) { l; } else { r--; } } return res; } }public class Solution { public int MaxArea(int[] heights) { int res 0; int l 0, r heights.Length-1; while (l r){ int area (Math.Min(heights[l], heights[r])) * (r - l); res Math.Max(area, res); if (heights[l] heights[r]){ l; } else{ r--; } } return res; } }func maxArea(heights []int) int { l, r : 0, len(heights) - 1 res : 0 for l r { area : min(heights[l], heights[r]) * (r - l) if area res { res area } if heights[l] heights[r] { l } else { r-- } } return res } func min(a, b int) int { if a b { return a } return b }class Solution { fun maxArea(heights: IntArray): Int { var l 0 var r heights.size - 1 var res 0 while (l r) { val area minOf(heights[l], heights[r]) * (r - l) res maxOf(res, area) if (heights[l] heights[r]) { l } else { r-- } } return res } }class Solution { func maxArea(_ heights: [Int]) - Int { var l 0, r heights.count - 1 var res 0 while l r { let area min(heights[l], heights[r]) * (r - l) res max(res, area) if heights[l] heights[r] { l 1 } else { r - 1 } } return res } }impl Solution { pub fn max_area(heights: Veci32) - i32 { let mut l 0usize; let mut r heights.len() - 1; let mut res 0; while l r { let area heights[l].min(heights[r]) * (r - l) as i32; res res.max(area); if heights[l] heights[r] { l 1; } else { r - 1; } } res } }时间与空间复杂度时间复杂度$O(n)$每个元素至多被指针访问一次指针总共移动 $n$ 次。空间复杂度$O(1)$只使用了l、r、res等常数个变量。仓库源码印证14 种语言的实现细节本仓库为该题提供了 14 种语言的实现文件统一命名0011-container-with-most-water.*与 README.md 中的解题索引体系一致。从源码结构看所有实现均采用双指针方案且与文档算法一一对应。这里选取几个有代表性的实现说明语言层面的差异细节Python条件分支的等价写法python/0011-container-with-most-water.py 将文档中的单层判断改写为显式双分支if height[l] height[r]: l 1 elif height[r] height[l]: r - 1height[l] height[r]时移动左指针height[r] height[l]时移动右指针。两种写法在两线等高时行为不同文档写法移动左指针仓库 Python 写法移动右指针。由于等高时移动任何一侧新容器高度都不超过该等值高度、宽度又减少面积不可能超过当前值因此两种分支策略结果完全一致。C手写 min/maxc/0011-container-with-most-water.c 在文件末尾显式注释说明C 语言没有预定义的 min 和 max 函数并手动实现int max(int a, int b) { return (a b) ? a : b; } int min(int a, int b) { return (a b) ? a : b; }这与 Go 版本 go/0011-container-with-most-water.go 中自建min辅助函数是同一类语言约束下的应对方式。Rust类型转换与指针类型rust/0011-container-with-most-water.rs 中左指针被显式声明为usize无符号类型r初始化为height.len() - 1由于乘法两边类型需一致宽度(r - l)通过as i32转为有符号整数后再与高度相乘let area heights[l].min(heights[r]) * (r - l) as i32;带复杂度注释的实现部分语言的源码直接以注释形式标注了复杂度例如 scala/0011-container-with-most-water.scala 与 dart/0011-container-with-most-water.dart 文件头部均写明// Time Complexity: O(n)、// Space Complexity: O(1)与本文双指针解法的复杂度结论相互印证。其余实现还包括 cpp/0011-container-with-most-water.cpp、csharp/0011-container-with-most-water.cs、javascript/0011-container-with-most-water.js、kotlin/0011-container-with-most-water.kt、ruby/0011-container-with-most-water.rb、swift/0011-container-with-most-water.swift、typescript/0011-container-with-most-water.ts算法骨架完全一致可交叉阅读对比各语言的语法风格。常见陷阱Common Pitfalls原文档在末尾专门列出了三类高频错误这里结合代码逐一说明1. 移动错误的指针算法要求必须移动较矮一侧的指针向内。如果误移动较高一侧的指针容器高度仍由较矮线决定高度不变宽度却必然减小面积只会变小且可能跳过真正的最优解。以heights [1, 8, 6, 2, 5, 4, 8, 3, 7]为例初始l 0高度 1、r 8高度 7若移动右指针而非左指针就永远无法排除掉高度 1 这根无效的矮线进而可能遗漏由两根高线构成的最大面积 49。2. 与「接雨水」混淆本仓库同时收录了 trapping-rain-waterTrapping Rain Water的题解。注意二者的本质区别盛最多水的容器只求一对竖线围成的单个容器最大面积接雨水需要累加每一段凹槽中能存下的水量。把接雨水的逐格累加心智模型套用到本题会导致面积计算错误。刷题时建议将这两题放在一起对比学习但务必区分目标函数。3. 宽度计算的 off-by-one 错误下标l与r之间的宽度是r - l而不是r - l 1。若误用后者每一对容器的面积都会被高估一个单位。以heights [1, 1]为例正确面积为min(1, 1) * (1 - 0) 1若写成(1 - 0 1) * 1 2结果就是错误的。双指针循环条件l r与宽度公式r - l是一对自洽的定义修改任何一处都要同步检查另一处。总结与延伸维度暴力枚举双指针核心思想枚举所有竖线对两端指针向中间收敛丢弃较矮侧时间复杂度$O(n^2)$$O(n)$空间复杂度$O(1)$$O(1)$适用场景验证思路、小规模数据面试与竞赛的标准解「盛最多水的容器」是双指针思想的经典入门题它不依赖排序、不依赖哈希表仅凭容器高度受短板限制这一条物理直觉就能把 $O(n^2)$ 降到 $O(n)$。掌握它之后可以进一步研究仓库中同样基于双指针的 two-integer-sum-ii、trapping-rain-water 等题目体会从两端逼近、按条件丢弃候选这一通用范式的威力。【免费下载链接】leetcodeLeetcode solutions项目地址: https://gitcode.com/GitHub_Trending/leetcode1/leetcode创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考