尧图网站建设 
LeetCode 11. 盛最多水的容器双指针面积公式、正确性证明与 Python/Java/C 实现详解LeetCode-Book 配套题解【免费下载链接】LeetCode-Book《剑指 Offer》《图解算法数据结构》《Krahets 笔面试精选 88 题》Python, Java, C 解题代码项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Book导读本篇技术指南以 LeetCode-Book 仓库中 《Krahets 笔面试精选 88 题》题解文档 为主体深入讲解经典高频笔试题11. 盛最多水的容器Container With Most Water的求解思路。文章将从水槽面积由短板决定这一核心观察出发推导面积公式给出双指针收窄策略、严格的正确性证明与复杂度分析并结合本仓库selected_coding_interview/codes下的 Python、Java、C 三语言源码进行逐行印证。读完本文你将掌握移动短板而非长板这一双指针贪心的本质并能在面试中流畅地复述其证明过程。一、问题定义与核心观察给定一个长度为n的整数数组height数组中的每个元素代表坐标点(i, height[i])处的一条垂直线。需要从中找出两条线使其与x轴共同构成的容器可以容纳最多的水即最大化容器面积返回容器可以储存的最大水量。说明容器不能倾斜且容器盛水量由两条垂直线中较矮的那条决定。题目本质是在所有下标对(i, j)其中i j中最大化min(height[i], height[j]) × (j - i)。在 LeetCode-Book 仓库中本题题解文档位于 selected_coding_interview/docs/11. 盛最多水的容器.md配套的三语言实现分别位于Pythonselected_coding_interview/codes/python/lc_11_container_with_most_water.pyJavaselected_coding_interview/codes/java/lc_11_container_with_most_water/lc_11_container_with_most_water.javaCselected_coding_interview/codes/cpp/lc_11_container_with_most_water/lc_11_container_with_most_water_s1.cpp二、面积公式容器高度由短板决定设两个指针i、j分别指向水槽的两块板板高分别为h[i]、h[j]此状态下水槽面积为S(i, j)。由于可容纳水的高度由两板中的短板决定水会从矮的一侧溢出因此可得如下面积公式S(i, j) min(h[i], h[j]) × (j - i)这个公式是整道题的基石面积 短板高度 × 底边宽度无论长板有多高只要短板不变面积上界就不会突破因此任何一次状态转移只有抬高短板或保持短板才可能让面积变大而降低或维持短板且缩短底边一定让面积变小。三、双指针直觉为什么必须移动短板在每个状态下无论长板或短板向中间收窄一格都会导致水槽底边宽度 -1 变短。此时关键在于分析min(h[i], h[j])的变化移动策略短板min(h[i], h[j])的变化对下一个水槽面积的影响向内移动短板可能变大下个水槽的面积可能增大向内移动长板不变或变小下个水槽的面积一定变小直觉解释若移动短板新的短板可能比原来更高即使底边变短面积仍有可能超过当前值存在变优的潜力若移动长板短板没有变高甚至变矮底边又缩短了乘积必然不增反减属于稳亏不赚的操作可以直接排除。因此正确的贪心策略是初始化双指针分列水槽左右两端循环每轮将短板向内移动一格并更新面积最大值直到两指针相遇时跳出即可获得最大面积。这一策略从每轮都排除掉一批不可能更优的状态的角度看本质上是一种高效的剪枝式双指针而非盲目枚举。四、算法流程按题解文档 selected_coding_interview/docs/11. 盛最多水的容器.md 的归纳算法流程如下初始化双指针i、j分列水槽左右两端i 0j n - 1循环收窄直至双指针相遇i j时跳出每轮执行更新面积最大值resres max(res, min(height[i], height[j]) × (j - i))选定两板高度中的短板向中间收窄一格height[i] height[j]时i否则j--返回值返回面积最大值res即可。整个过程只需一次线性扫描指针相遇即终止无需回溯。五、正确性证明若暴力枚举水槽两板围成面积S(i, j)的状态总数为C(n, 2)即从n块板中任选两块的所有组合。双指针法之所以能保证不丢最优解依据如下假设状态S(i, j)下h[i] h[j]左板为短板此时向内移动短板至S(i 1, j)则相当于一次性消去了状态集合{S(i, j-1), S(i, j-2), ..., S(i, i1)}——即以左板i为固定端、右端从j-1一路收到i1的所有组合。而所有被消去的状态其面积一定都小于当前面积即 S(i, j)因为短板高度相比S(i, j)相同或更短即≤ h[i]。右板收窄后不可能出现比h[i]更高的新短板因为h[i]就是当前短板底边宽度相比S(i, j)更短右端从j收缩到了j-1及更左。面积由短板高度与底边宽度相乘得到两者都不增故这些被消去状态的面积均严格小于当前面积。因此每轮向内移动短板所有消去的状态都不会导致面积最大值丢失证毕。对称地当h[i] h[j]右板为短板时移动右板j--可消去{S(i1, j), ..., S(j-1, j)}状态集合论证同理。一句话总结短板决定了面积的上界固定短板时无论另一侧如何收缩都不可能超过当前面积所以每轮可以安全地淘汰短板一侧的所有状态。六、复杂度分析时间复杂度O(N)双指针遍历一次底边宽度N每轮仅做常数次比较与更新空间复杂度O(1)仅使用变量i、j、res等常数额外空间。对比暴力枚举的O(N²)时间复杂度双指针法将问题从平方级优化到线性级这也是该题在面试中被反复考察的核心价值所在。七、三语言代码实现含仓库源码印证Python 实现仓库源码 selected_coding_interview/codes/python/lc_11_container_with_most_water.py 与题解文档中的代码完全一致class Solution: def maxArea(self, height: List[int]) - int: i, j, res 0, len(height) - 1, 0 while i j: if height[i] height[j]: res max(res, height[i] * (j - i)) i 1 else: res max(res, height[j] * (j - i)) j - 1 return res实现要点List类型注解来自仓库的公共 include 模块 selected_coding_interview/codes/python/include/init.py该模块统一导出List、Optional、链表与二叉树工具类等当height[i] height[j]时移动左指针否则含相等情形移动右指针保证每轮一定移动短板相等时移动任意一侧均可因为此时无论移动哪边新状态的面积都不可能超过当前值。仓库同目录下的驱动代码还给出了可直接运行的测试用例test_input [1, 2, 3, 4, 5]期望输出为6选择下标1与4即min(2, 5) × 3 6。运行方式python selected_coding_interview/codes/python/lc_11_container_with_most_water.pyJava 实现仓库源码 selected_coding_interview/codes/java/lc_11_container_with_most_water/lc_11_container_with_most_water.javaclass Solution { public int maxArea(int[] height) { int i 0, j height.length - 1, res 0; while(i j) { res height[i] height[j] ? Math.max(res, (j - i) * height[i]): Math.max(res, (j - i) * height[j--]); } return res; } }实现要点利用三元表达式与i/j--的自增自减副作用在一行内同时完成取短板、计算面积、移动指针三件事写法精炼注意自增运算的求值顺序(j - i) * height[i]中先以当前i计算面积随后i才自增语义与显式写法完全等价仓库中的驱动类main同样以[1, 2, 3, 4, 5]作为测试输入并打印结果。C 实现仓库源码 selected_coding_interview/codes/cpp/lc_11_container_with_most_water/lc_11_container_with_most_water_s1.cppclass Solution { public: int maxArea(vectorint height) { int i 0, j height.size() - 1, res 0; while(i j) { res height[i] height[j] ? max(res, (j - i) * height[i]): max(res, (j - i) * height[j--]); } return res; } };实现要点与 Java 版结构几乎一致同样利用?:与自增表达式压缩代码该文件通过#include ../include/include.hpp引入仓库公共头文件vectorint为按引用传入避免拷贝开销注意height可能为vector而非原始数组height.size()返回size_t减法后赋值给int时在n 1前提下是安全的。三份实现均只使用O(1)额外空间逻辑完全等价可互相印证。八、延伸思考为什么从两端开始只有从最宽底边出发才能在逐步收窄的过程中不遗漏宽底边 × 高短板的候选组合若从中间出发则无法系统地剪枝。相等高度的处理当height[i] height[j]时代码默认移动右指针由于此时两板等矮无论移动哪侧被淘汰的状态都不含更优解因此不影响正确性。与二分/贪心的关系本题双指针并非严格二分而是每轮依据短板决定面积上界的单调性剪枝是每轮必淘汰一侧无望状态的贪心式双指针常与 LC 167. 两数之和 II、LC 240. 搜索二维矩阵 II 等题目归为同一类相向双指针套路。九、总结维度结论面积公式S(i, j) min(h[i], h[j]) × (j - i)指针策略每轮移动短板一侧向中间收窄正确性移动短板可安全淘汰所有不可能更优的状态时间复杂度O(N)空间复杂度O(1)仓库代码Python / Java / C 三语言实现均带驱动与测试用例本文以 LeetCode-Book 仓库题解文档为核心完整覆盖了面积公式、双指针流程、严格正确性证明、复杂度分析并通过 Python、Java、C 三份仓库源码逐行印证。掌握短板决定面积、移动短板、线性剪枝这一完整推理链即可在面试中对此题做到既会写代码也能讲清楚为什么这样写是对的。【免费下载链接】LeetCode-Book《剑指 Offer》《图解算法数据结构》《Krahets 笔面试精选 88 题》Python, Java, C 解题代码项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Book创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考 LeetCode 11. 盛最多水的容器｜双指针面积公式、正确性证明与 Python/Java/C++ 实现详解（LeetCode-Book 配套题解）
LeetCode 11. 盛最多水的容器双指针面积公式、正确性证明与 Python/Java/C 实现详解LeetCode-Book 配套题解【免费下载链接】LeetCode-Book《剑指 Offer》《图解算法数据结构》《Krahets 笔面试精选 88 题》Python, Java, C 解题代码项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Book导读本篇技术指南以 LeetCode-Book 仓库中 《Krahets 笔面试精选 88 题》题解文档 为主体深入讲解经典高频笔试题11. 盛最多水的容器Container With Most Water的求解思路。文章将从水槽面积由短板决定这一核心观察出发推导面积公式给出双指针收窄策略、严格的正确性证明与复杂度分析并结合本仓库selected_coding_interview/codes下的 Python、Java、C 三语言源码进行逐行印证。读完本文你将掌握移动短板而非长板这一双指针贪心的本质并能在面试中流畅地复述其证明过程。一、问题定义与核心观察给定一个长度为n的整数数组height数组中的每个元素代表坐标点(i, height[i])处的一条垂直线。需要从中找出两条线使其与x轴共同构成的容器可以容纳最多的水即最大化容器面积返回容器可以储存的最大水量。说明容器不能倾斜且容器盛水量由两条垂直线中较矮的那条决定。题目本质是在所有下标对(i, j)其中i j中最大化min(height[i], height[j]) × (j - i)。在 LeetCode-Book 仓库中本题题解文档位于 selected_coding_interview/docs/11. 盛最多水的容器.md配套的三语言实现分别位于Pythonselected_coding_interview/codes/python/lc_11_container_with_most_water.pyJavaselected_coding_interview/codes/java/lc_11_container_with_most_water/lc_11_container_with_most_water.javaCselected_coding_interview/codes/cpp/lc_11_container_with_most_water/lc_11_container_with_most_water_s1.cpp二、面积公式容器高度由短板决定设两个指针i、j分别指向水槽的两块板板高分别为h[i]、h[j]此状态下水槽面积为S(i, j)。由于可容纳水的高度由两板中的短板决定水会从矮的一侧溢出因此可得如下面积公式S(i, j) min(h[i], h[j]) × (j - i)这个公式是整道题的基石面积 短板高度 × 底边宽度无论长板有多高只要短板不变面积上界就不会突破因此任何一次状态转移只有抬高短板或保持短板才可能让面积变大而降低或维持短板且缩短底边一定让面积变小。三、双指针直觉为什么必须移动短板在每个状态下无论长板或短板向中间收窄一格都会导致水槽底边宽度 -1 变短。此时关键在于分析min(h[i], h[j])的变化移动策略短板min(h[i], h[j])的变化对下一个水槽面积的影响向内移动短板可能变大下个水槽的面积可能增大向内移动长板不变或变小下个水槽的面积一定变小直觉解释若移动短板新的短板可能比原来更高即使底边变短面积仍有可能超过当前值存在变优的潜力若移动长板短板没有变高甚至变矮底边又缩短了乘积必然不增反减属于稳亏不赚的操作可以直接排除。因此正确的贪心策略是初始化双指针分列水槽左右两端循环每轮将短板向内移动一格并更新面积最大值直到两指针相遇时跳出即可获得最大面积。这一策略从每轮都排除掉一批不可能更优的状态的角度看本质上是一种高效的剪枝式双指针而非盲目枚举。四、算法流程按题解文档 selected_coding_interview/docs/11. 盛最多水的容器.md 的归纳算法流程如下初始化双指针i、j分列水槽左右两端i 0j n - 1循环收窄直至双指针相遇i j时跳出每轮执行更新面积最大值resres max(res, min(height[i], height[j]) × (j - i))选定两板高度中的短板向中间收窄一格height[i] height[j]时i否则j--返回值返回面积最大值res即可。整个过程只需一次线性扫描指针相遇即终止无需回溯。五、正确性证明若暴力枚举水槽两板围成面积S(i, j)的状态总数为C(n, 2)即从n块板中任选两块的所有组合。双指针法之所以能保证不丢最优解依据如下假设状态S(i, j)下h[i] h[j]左板为短板此时向内移动短板至S(i 1, j)则相当于一次性消去了状态集合{S(i, j-1), S(i, j-2), ..., S(i, i1)}——即以左板i为固定端、右端从j-1一路收到i1的所有组合。而所有被消去的状态其面积一定都小于当前面积即 S(i, j)因为短板高度相比S(i, j)相同或更短即≤ h[i]。右板收窄后不可能出现比h[i]更高的新短板因为h[i]就是当前短板底边宽度相比S(i, j)更短右端从j收缩到了j-1及更左。面积由短板高度与底边宽度相乘得到两者都不增故这些被消去状态的面积均严格小于当前面积。因此每轮向内移动短板所有消去的状态都不会导致面积最大值丢失证毕。对称地当h[i] h[j]右板为短板时移动右板j--可消去{S(i1, j), ..., S(j-1, j)}状态集合论证同理。一句话总结短板决定了面积的上界固定短板时无论另一侧如何收缩都不可能超过当前面积所以每轮可以安全地淘汰短板一侧的所有状态。六、复杂度分析时间复杂度O(N)双指针遍历一次底边宽度N每轮仅做常数次比较与更新空间复杂度O(1)仅使用变量i、j、res等常数额外空间。对比暴力枚举的O(N²)时间复杂度双指针法将问题从平方级优化到线性级这也是该题在面试中被反复考察的核心价值所在。七、三语言代码实现含仓库源码印证Python 实现仓库源码 selected_coding_interview/codes/python/lc_11_container_with_most_water.py 与题解文档中的代码完全一致class Solution: def maxArea(self, height: List[int]) - int: i, j, res 0, len(height) - 1, 0 while i j: if height[i] height[j]: res max(res, height[i] * (j - i)) i 1 else: res max(res, height[j] * (j - i)) j - 1 return res实现要点List类型注解来自仓库的公共 include 模块 selected_coding_interview/codes/python/include/init.py该模块统一导出List、Optional、链表与二叉树工具类等当height[i] height[j]时移动左指针否则含相等情形移动右指针保证每轮一定移动短板相等时移动任意一侧均可因为此时无论移动哪边新状态的面积都不可能超过当前值。仓库同目录下的驱动代码还给出了可直接运行的测试用例test_input [1, 2, 3, 4, 5]期望输出为6选择下标1与4即min(2, 5) × 3 6。运行方式python selected_coding_interview/codes/python/lc_11_container_with_most_water.pyJava 实现仓库源码 selected_coding_interview/codes/java/lc_11_container_with_most_water/lc_11_container_with_most_water.javaclass Solution { public int maxArea(int[] height) { int i 0, j height.length - 1, res 0; while(i j) { res height[i] height[j] ? Math.max(res, (j - i) * height[i]): Math.max(res, (j - i) * height[j--]); } return res; } }实现要点利用三元表达式与i/j--的自增自减副作用在一行内同时完成取短板、计算面积、移动指针三件事写法精炼注意自增运算的求值顺序(j - i) * height[i]中先以当前i计算面积随后i才自增语义与显式写法完全等价仓库中的驱动类main同样以[1, 2, 3, 4, 5]作为测试输入并打印结果。C 实现仓库源码 selected_coding_interview/codes/cpp/lc_11_container_with_most_water/lc_11_container_with_most_water_s1.cppclass Solution { public: int maxArea(vectorint height) { int i 0, j height.size() - 1, res 0; while(i j) { res height[i] height[j] ? max(res, (j - i) * height[i]): max(res, (j - i) * height[j--]); } return res; } };实现要点与 Java 版结构几乎一致同样利用?:与自增表达式压缩代码该文件通过#include ../include/include.hpp引入仓库公共头文件vectorint为按引用传入避免拷贝开销注意height可能为vector而非原始数组height.size()返回size_t减法后赋值给int时在n 1前提下是安全的。三份实现均只使用O(1)额外空间逻辑完全等价可互相印证。八、延伸思考为什么从两端开始只有从最宽底边出发才能在逐步收窄的过程中不遗漏宽底边 × 高短板的候选组合若从中间出发则无法系统地剪枝。相等高度的处理当height[i] height[j]时代码默认移动右指针由于此时两板等矮无论移动哪侧被淘汰的状态都不含更优解因此不影响正确性。与二分/贪心的关系本题双指针并非严格二分而是每轮依据短板决定面积上界的单调性剪枝是每轮必淘汰一侧无望状态的贪心式双指针常与 LC 167. 两数之和 II、LC 240. 搜索二维矩阵 II 等题目归为同一类相向双指针套路。九、总结维度结论面积公式S(i, j) min(h[i], h[j]) × (j - i)指针策略每轮移动短板一侧向中间收窄正确性移动短板可安全淘汰所有不可能更优的状态时间复杂度O(N)空间复杂度O(1)仓库代码Python / Java / C 三语言实现均带驱动与测试用例本文以 LeetCode-Book 仓库题解文档为核心完整覆盖了面积公式、双指针流程、严格正确性证明、复杂度分析并通过 Python、Java、C 三份仓库源码逐行印证。掌握短板决定面积、移动短板、线性剪枝这一完整推理链即可在面试中对此题做到既会写代码也能讲清楚为什么这样写是对的。【免费下载链接】LeetCode-Book《剑指 Offer》《图解算法数据结构》《Krahets 笔面试精选 88 题》Python, Java, C 解题代码项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Book创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考