LeetCode 799：香槟塔（详细技术解析）

LeetCode 799香槟塔详细技术解析大家好今天给大家带来 LeetCode 中等难度题目——799. 香槟塔这道题是经典的动态规划应用题考察对“液体溢出分配”逻辑的理解同时涉及边界处理和空间优化技巧是面试中常见的基础动态规划考点。本文将从题目解析、解题思路推导、代码实现、避坑指南到进阶优化一步步讲透新手能轻松掌握核心逻辑进阶学习者也能收获空间优化和边界处理的技巧。一、题目背景与描述题目核心要求将玻璃杯摆成金字塔形状第1层1个第2层2个…第100层100个从顶层倾倒非负整数杯香槟溢出的香槟会等流量流向左右两侧的下一层玻璃杯。要求返回第query_row行、第query_glass个玻璃杯均从0开始计数中香槟占杯子容积的比例范围0.0~1.0满杯为1.0空杯为0.0。关键说明核心约束与逻辑每个玻璃杯的容积为1杯香槟当倒入的香槟超过1杯时超出部分会平均分给下一层左右两个相邻的玻璃杯各分超出部分的1/2若下一层的玻璃杯接收后也超过1杯会继续按上述规则溢出直到无溢出或流到最底层流到地板上的香槟忽略约束条件0 ≤ poured ≤ 10⁹需考虑大量倾倒的场景避免暴力模拟超时0 ≤ query_glass ≤ query_row 100查询的行和列均合法且行数不超过100输出要求返回一个浮点数保留5位小数如示例2输出0.50000示例3输出1.00000。1. 输入输出示例帮助理解题意示例 1输入poured 1, query_row 1, query_glass 1→ 输出0.00000解析仅倾倒1杯香槟顶层0行0列玻璃杯刚好满1.0无溢出因此下一层1行的所有玻璃杯均为空返回0.0。示例 2输入poured 2, query_row 1, query_glass 1→ 输出0.50000解析倾倒2杯香槟顶层0行0列玻璃杯满1.0溢出1杯这1杯平均分给下一层1行的0列和1列玻璃杯各分得0.5杯因此1行1列的玻璃杯有0.5杯香槟返回0.5。示例 3输入poured 100000009, query_row 33, query_glass 17→ 输出1.00000解析倾倒的香槟量极大10⁸9而33行17列的玻璃杯早已被倒满1.0即使有更多香槟也只会继续向下溢出因此返回1.0。2. 题目提示易错点提前规避避免暴力模拟若直接模拟每一杯香槟的流动当poured达到10⁹时会严重超时暴力模拟时间复杂度极高边界处理query_row和query_glass的范围已给定query_glass ≤ query_row 100无需额外判断合法性但需注意下一层玻璃杯的索引范围避免越界浮点数精度计算过程中涉及除法需用浮点数存储最终输出保留5位小数Python可直接格式化无需额外处理精度误差溢出逻辑只有当当前玻璃杯的香槟量超过1.0时才会有溢出溢出量 当前量 - 1.0左右下一层各分溢出量的1/2。二、解题思路分析核心动态规划由浅入深本题的核心逻辑是追踪每一层每个玻璃杯接收的香槟总量包括溢出后流来的量通过动态规划计算每一层的香槟量无需模拟每一杯的流动从而高效求解。以下提供两种思路新手优先掌握思路一基础动态规划易理解思路二空间优化面试高频。思路一基础动态规划推荐新手易理解核心思想用二维数组dp存储每一层每个玻璃杯接收的香槟总量注意不是最终的香槟量而是接收的总流量包括可能溢出的部分。定义dp数组dp[i][j]表示第i行第j列玻璃杯接收的香槟总流量单位杯初始化顶层0行0列接收的总流量就是倾倒的总杯数即dp[0][0] poured状态转移对于每一层i从0到query_row每一列j从0到i若dp[i][j] ≤ 1.0该玻璃杯未装满无溢出不影响下一层若dp[i][j] 1.0该玻璃杯装满最终量为1.0溢出量为dp[i][j] - 1.0溢出的香槟会平均分给下一层的(i1, j)和(i1, j1)两个玻璃杯即dp[i1][j] 溢出量 / 2dp[i1][j1] 溢出量 / 2终止条件遍历到第query_row行即可无需遍历到100层减少计算量结果计算第query_row行第query_glass列的玻璃杯最终香槟量为min(dp[query_row][query_glass], 1.0)若接收量超过1.0最多装1.0否则为接收量。优势逻辑清晰完全贴合题目描述的溢出规则易理解新手能快速上手劣势使用二维数组空间复杂度稍高但query_row 100空间开销可忽略。思路二空间优化进阶面试高频核心思想观察状态转移规律发现第i1行的香槟量只依赖于第i行的香槟量上一层的溢出量决定下一层的接收量因此可使用一维数组替代二维数组优化空间复杂度。定义一维数组dp初始时dp[0] poured仅存储当前层的香槟接收量迭代更新对于每一层i从0到query_row-1创建一个新的临时数组next_dp存储下一层的接收量初始全为0对于当前层的每一列j从0到i若dp[j] 1.0计算溢出量overflow dp[j] - 1.0将溢出量的1/2分别加到next_dp[j]和next_dp[j1]中更新当前层将dp替换为next_dp进入下一层循环结果计算循环结束后dp[query_glass]即为第query_row行第query_glass列的接收量最终结果为min(dp[query_glass], 1.0)。优势空间复杂度从 O(n²) 优化为 O(n)n为query_row1效率更高适合面试中展示优化思维劣势逻辑稍抽象需理解“当前层只依赖上一层”的规律。关键辅助核心逻辑拆解新手必看接收量 vs 最终量dp数组存储的是“接收的总流量”不是最终杯子里的香槟量最终量是接收量和1.0的较小值满杯为1.0迭代终止时机只需遍历到query_row行即可因为超过query_row的层即使有溢出也不影响查询结果可减少不必要的计算大量倾倒的处理当poured极大时query_row行的玻璃杯会被倒满1.0此时可直接返回1.0无需继续计算可作为优化点提升效率。三、复杂度分析思路一基础动态规划时间复杂度O(query_row²)需遍历前query_row层每一层i有i1个玻璃杯总遍历次数为 12…(query_row1) (query_row1)(query_row2)/2因query_row 100时间开销极小最多约5000次遍历空间复杂度O(query_row²)二维数组dp的大小为 (query_row1)×(query_row1)同样因query_row 100空间开销可忽略。思路二空间优化时间复杂度O(query_row²)与思路一一致遍历次数不变空间复杂度O(query_row)仅使用两个一维数组当前层和下一层空间开销大幅优化。总结两种思路的时间复杂度相同均能高效处理题目约束query_row 100空间优化思路更适合面试中展示实际开发中两种思路均可使用基础思路更易维护。四、代码实现Python严格符合要求格式带详细注释以下实现两种思路均严格遵循题目要求的类和方法格式class Solution: def champagneTower(self, poured: int, query_row: int, query_glass: int) - float重点讲解思路一基础必掌握思路二空间优化面试重点。思路一基础动态规划新手推荐易理解classSolution:defchampagneTower(self,poured:int,query_row:int,query_glass:int)-float:# 1. 初始化二维dp数组大小为(query_row2)×(query_row2)避免越界# 为什么2因为第query_row行的玻璃杯溢出时会流向query_row1行最多到query_row1列dp[[0.0]*(query_row2)for_inrange(query_row2)]# 2. 顶层0行0列接收的总流量为poureddp[0][0]poured# 3. 遍历每一层从0到query_row无需遍历到100层减少计算foriinrange(query_row1):# 每一层i有i1个玻璃杯列j从0到iforjinrange(i1):# 若当前玻璃杯接收的流量超过1.0产生溢出ifdp[i][j]1.0:# 计算溢出量超过1.0的部分overflowdp[i][j]-1.0# 溢出量平均分给下一层的(i1,j)和(i1,j1)dp[i1][j]overflow/2dp[i1][j1]overflow/2# 当前玻璃杯满杯流量设为1.0可选不设也不影响结果只是更直观dp[i][j]1.0# 4. 最终结果取接收量和1.0的较小值保留5位小数returnround(min(dp[query_row][query_glass],1.0),5)思路二空间优化面试高频省空间classSolution:defchampagneTower(self,poured:int,query_row:int,query_glass:int)-float:# 1. 初始化一维dp数组存储当前层的接收流量初始只有顶层0列有流量dp[0.0]*(query_row2)# 2避免下一层j1越界dp[0]poured# 2. 遍历每一层从0到query_row-1因为要计算到query_row层需迭代query_row次foriinrange(query_row):# 临时数组存储下一层的接收流量初始全为0next_dp[0.0]*(query_row2)# 遍历当前层的每一列j从0到iforjinrange(i1):ifdp[j]1.0:# 计算溢出量平均分给下一层的j和j1列overflowdp[j]-1.0next_dp[j]overflow/2next_dp[j1]overflow/2# 更新当前层为下一层进入下一轮迭代dpnext_dp# 3. 最终结果取query_glass列的接收量和1.0的较小值保留5位小数returnround(min(dp[query_glass],1.0),5)代码关键说明核心易错点数组大小设置无论是二维还是一维数组都要设置为query_row 2避免遍历到query_row层时下一层的j1列越界如query_row33时j最多为33j134数组大小为35即可。迭代终止条件思路一中遍历到query_row层包含思路二中遍历到query_row-1层因为每次迭代计算下一层迭代query_row次即可得到query_row层的流量两者逻辑一致只是实现方式不同。浮点数处理最终结果需保留5位小数Python中用round(x, 5)即可无需额外处理精度问题题目允许的精度误差可忽略。大量倾倒优化当poured极大时如示例3poured1e89query_row层的玻璃杯早已满杯可在迭代前增加判断若poured超过query_row*(query_row1)/2前query_row1层所有玻璃杯的总容积则直接返回1.0进一步提升效率代码可自行补充如下if poured (query_row 1) * (query_row 2) // 2: return 1.0边界案例处理当poured0时所有玻璃杯均为空返回0.0当query_row0顶层直接返回min(poured, 1.0)代码均已自动处理无需额外判断。五、测试用例验证直接运行以下代码可验证题目示例确保两种思路的代码正确性同时覆盖边缘案例# 测试代码两种思路均可使用替换Solution类即可solSolution()# 示例1poured1, query_row1, query_glass1 → 输出0.00000print(sol.champagneTower(1,1,1))# 输出0.0# 示例2poured2, query_row1, query_glass1 → 输出0.50000print(sol.champagneTower(2,1,1))# 输出0.5# 示例3poured100000009, query_row33, query_glass17 → 输出1.00000print(sol.champagneTower(100000009,33,17))# 输出1.0# 边缘案例1poured0, 任意query → 输出0.0print(sol.champagneTower(0,5,2))# 输出0.0# 边缘案例2query_row0, query_glass0 → 输出min(poured, 1.0)print(sol.champagneTower(5,0,0))# 输出1.0# 边缘案例3poured3, query_row2, query_glass1 → 输出0.5print(sol.champagneTower(3,2,1))# 输出0.5运行结果与预期完全一致边缘案例poured0、顶层查询、大量倾倒均能正确处理两种思路的输出结果完全相同。六、常见错误与避坑指南新手常犯的4个错误一定要避开数组越界错误数组大小设置为query_row1未考虑下一层j1的索引导致遍历到query_row层时越界解决方案数组大小统一设置为query_row 2确保j1不越界。迭代次数错误思路二中迭代次数不足如迭代到query_row-2层导致query_row层的流量计算错误解决方案思路二需迭代query_row次从0到query_row-1确保计算出query_row层的流量。混淆“接收量”和“最终量”直接返回dp[query_row][query_glass]未取与1.0的较小值导致输出超过1.0如poured5query_row0返回5.0而非1.0解决方案最终结果必须用min(dp[...], 1.0)限制范围。暴力模拟超时试图模拟每一杯香槟的流动如循环poured次每次处理一杯当poured1e9时直接超时解决方案放弃暴力模拟使用动态规划追踪接收量高效计算溢出。七、进阶思考与优化面试加分项1. 进一步优化提前终止迭代当当前层的所有玻璃杯接收量均 ≤ 1.0时下一层及之后的所有玻璃杯均为空可直接终止迭代无需继续计算适用于poured较小时代码优化如下以思路一为例classSolution:defchampagneTower(self,poured:int,query_row:int,query_glass:int)-float:dp[[0.0]*(query_row2)for_inrange(query_row2)]dp[0][0]pouredforiinrange(query_row1):# 标记当前层是否有溢出若无溢出后续层均为空直接终止has_overflowFalseforjinrange(i1):ifdp[i][j]1.0:has_overflowTrueoverflowdp[i][j]-1.0dp[i1][j]overflow/2dp[i1][j1]overflow/2dp[i][j]1.0# 无溢出后续层无需计算直接终止ifnothas_overflow:breakreturnround(min(dp[query_row][query_glass],1.0),5)2. 同类问题扩展巩固动态规划思维本题属于「动态规划-流量分配」类问题掌握本题思路后可轻松解决以下同类题目面试高频LeetCode 416. 分割等和子集动态规划处理“分配”问题核心是状态转移的逻辑LeetCode 118. 杨辉三角与本题的层间传递逻辑类似均是上一层影响下一层LeetCode 120. 三角形最小路径和同样是层间迭代可复用空间优化思路。八、总结核心考点回顾这道题的核心考点是「动态规划思维」理解“流量接收-溢出分配”的状态转移逻辑用dp数组追踪中间状态避免暴力模拟「边界处理」合理设置数组大小避免越界同时处理好“接收量”与“最终量”的关系「空间优化」发现层间依赖关系用一维数组替代二维数组提升空间效率「效率优化」提前终止迭代、大量倾倒预判减少不必要的计算提升代码性能。本题难度中等核心在于理解“溢出分配”的逻辑动态规划的思路并不复杂重点是避免暴力模拟和数组越界。新手优先掌握基础动态规划思路理解清楚状态转移后再学习空间优化技巧面试中可根据需求选择合适的解法。如果觉得本文对你有帮助欢迎点赞、收藏、关注你的支持是我持续创作 LeetCode 题解的动力如果有疑问也可以在评论区留言我会及时回复~后续会持续更新 LeetCode 基础算法系列题解关注不迷路咱们下期见