题目描述
思路解析
一句话答案：LeetCode 799 香槟塔逐行模拟：每杯满 1 后溢出的部分平分给正下方左右两杯，用滚动数组推到查询行，结果取 min(1, 该杯量)。时间 O(row²)、空间 O(row)。
查询那一杯，最终接住多少香槟
香槟从最顶端杯子倒进去，总量 poured 杯。每杯只能装满 1，多出的部分均匀流进正下方左右相邻的两杯。给你行号 query_row 和该行第几个杯子 query_glass，问倒完后这杯里有多少香槟，上限 1。poured=2 查第 1 行第 1 杯：顶杯满 1 剩 1 杯溢出、平分给下面两杯各 0.5，答案 0.5。
为什么盯着目标杯往上倒推会指数爆炸
只算目标那一杯：某杯的量 = 左上、右上两父杯溢出量之和，父杯又依赖它头上两杯。写成递归，每往上追一层就分叉成两支，追到第 query_row 行约 O(2^row) 次，中间父杯反复重算。既然每杯只由上一行相邻两杯决定，反过来从顶杯往下逐行填、每杯只算一次就够。
从顶杯逐行往下淌，一维数组存当前行
用一维数组 row 表示当前行的各杯，起手只有顶杯 row = [poured]。往下走一行，就新建一个比它长 1 的数组存下一行，把当前行每杯该溢的量灌进去，再把它当成新的当前行往下推到 query_row。数组里存的是「流经这杯的总量」，可能远大于 1——它得先超过 1 才有余量往下溢。每行算完就覆盖成下一行，这叫滚动数组（只留当前一行、循环覆盖旧值），空间从存整座塔 O(row²) 压到 O(row)。
溢出为什么除 2、下层为什么用累加
溢出量 over = max(0, x - 1) / 2：减 1 是它自己要先留满一杯，除 2 是溢出要平分给左右两杯、每个只得一半，忘了除 2 会让香槟凭空翻倍。
灌进下一行写 next[i] += over、next[i+1] += over，都用累加：下一行一杯会同时接到左上、右上两父杯的溢出，两股要加起来，直接赋值会覆盖先到那份、少算一半。
拿 poured=8 查第 3 行第 2 杯逐行算一遍
第 0 行只有顶杯 [8]。推第 1 行：顶杯 over=(8-1)/2=3.5 灌进下一行两杯，得 [3.5, 3.5]。推第 2 行：第 0 杯 over=(3.5-1)/2=1.25 加到第 0、1 杯，第 1 杯 over=1.25 加到第 1、2 杯；第 1 杯接到左右两股累计 1.25+1.25=2.5，得 [1.25, 2.5, 1.25]。
推第 3 行：第 0 杯 over=(1.25-1)/2=0.125、第 1 杯 over=(2.5-1)/2=0.75、第 2 杯 over=0.125，各加给相邻两杯，得 [0.125, 0.875, 0.875, 0.125]。读第 2 杯，min(1, 0.875)=0.875 即答案。
推到第几行要多少次，除 2 和 min 别丢
从第 0 行推到第 query_row 行，各行杯子数累加约 row²/2 次，时间 O(row²)；滚动数组只存一行，空间 O(row)。poured=0 时全塔为 0、查询返回 0；query_row=0 还没溢出，答案就是 min(1, poured)——这两处别漏。收尾 min 也不能提前做——途中若把超过 1 的杯子压到 1，它就没余量往下溢、下层会少算，只有读答案那刻才 min。
▶ 动画逐步走查（文字版）——想跟着上方动画一帧帧对照就展开
记住口诀:「满 1 才溢,溢出平分给下面两杯」,下面逐杯套它。
先把全部 8 杯香槟倒进顶杯:第 0 行只有 1 个杯子,里面是 8(紫)。它远远超过 1,接下来会大量溢出。其余行暂时都是空的(0)。
现在看第 0 行(蓝)的每个杯子。凡是超过 1 的,多出来的部分要平分流进第 1 行紧挨它的左右两杯。第 1 行此刻还是空的,等着接香槟。
看第 0 行第 0 个杯子(紫),里面有 8,超过 1。多出来的 8 - 1 = 7 平分成两份,每份 3.5,分别流向下一行第 0、第 1 个杯子。
把 3.5 同时灌进第 1 行的第 0 杯和第 1 杯(绿,它们现在分别累计到 3.5 和 3.5)。同一个下层杯子可能同时接到左上、右上两个杯子的溢出,所以用累加。
第 0 行所有杯子都处理过了。第 1 行现在是 [3.5, 3.5](绿)。继续往下一行递推。
现在看第 1 行(蓝)的每个杯子。凡是超过 1 的,多出来的部分要平分流进第 2 行紧挨它的左右两杯。第 2 行此刻还是空的,等着接香槟。
看第 1 行第 0 个杯子(紫),里面有 3.5,超过 1。多出来的 3.5 - 1 = 2.5 平分成两份,每份 1.25,分别流向下一行第 0、第 1 个杯子。
把 1.25 同时灌进第 2 行的第 0 杯和第 1 杯(绿,它们现在分别累计到 1.25 和 1.25)。同一个下层杯子可能同时接到左上、右上两个杯子的溢出,所以用累加。
看第 1 行第 1 个杯子(紫),里面有 3.5,超过 1。多出来的 3.5 - 1 = 2.5 平分成两份,每份 1.25,分别流向下一行第 1、第 2 个杯子。
把 1.25 同时灌进第 2 行的第 1 杯和第 2 杯(绿,它们现在分别累计到 2.5 和 1.25)。同一个下层杯子可能同时接到左上、右上两个杯子的溢出,所以用累加。
第 1 行所有杯子都处理过了。第 2 行现在是 [1.25, 2.5, 1.25](绿)。继续往下一行递推。
现在看第 2 行(蓝)的每个杯子。凡是超过 1 的,多出来的部分要平分流进第 3 行紧挨它的左右两杯。第 3 行此刻还是空的,等着接香槟。
看第 2 行第 0 个杯子(紫),里面有 1.25,超过 1。多出来的 1.25 - 1 = 0.25 平分成两份,每份 0.125,分别流向下一行第 0、第 1 个杯子。
把 0.125 同时灌进第 3 行的第 0 杯和第 1 杯(绿,它们现在分别累计到 0.125 和 0.125)。同一个下层杯子可能同时接到左上、右上两个杯子的溢出,所以用累加。
看第 2 行第 1 个杯子(紫),里面有 2.5,超过 1。多出来的 2.5 - 1 = 1.5 平分成两份,每份 0.75,分别流向下一行第 1、第 2 个杯子。
把 0.75 同时灌进第 3 行的第 1 杯和第 2 杯(绿,它们现在分别累计到 0.875 和 0.75)。同一个下层杯子可能同时接到左上、右上两个杯子的溢出,所以用累加。
看第 2 行第 2 个杯子(紫),里面有 1.25,超过 1。多出来的 1.25 - 1 = 0.25 平分成两份,每份 0.125,分别流向下一行第 2、第 3 个杯子。
把 0.125 同时灌进第 3 行的第 2 杯和第 3 杯(绿,它们现在分别累计到 0.875 和 0.125)。同一个下层杯子可能同时接到左上、右上两个杯子的溢出,所以用累加。
第 2 行所有杯子都处理过了。第 3 行现在是 [0.125, 0.875, 0.875, 0.125](绿)。已经推到查询的第 3 行,接下来直接读取第 2 个杯子并对 1 取 min。
推到查询的第 3 行,看第 2 个杯子(紫):里面累计到 0.875。杯子最多装 1 杯,所以取 min(1, 0.875) = 0.875。这就是最终答案。
回顾整条链:8 杯从顶杯一路溢下来,每层「满 1 才溢、溢出平分给下面两杯」。查询的杯子(紫)最终是 0.875。整道题的核心就是从上到下逐行模拟这一个溢出规则。
边界:倒 0 全是 0;查第 0 行就是 min(1, poured);倒太多则该杯封顶为 1。
两个追问:滚动数组靠「只依赖上一行」;模拟途中不能提前封顶,只在读答案时取 min。
参考代码
class Solution: def champagneTower(self, poured: int, query_row: int, query_glass: int) -> float: row = [float(poured)] for _ in range(query_row): nxt = [0.0] * (len(row) + 1) for i, x in enumerate(row): over = max(0.0, x - 1.0) / 2.0 nxt[i] += over nxt[i + 1] += over row = nxt return min(1.0, row[query_glass])复杂度
- 时间：O(row²)，从第 0 行推到第 query_row 行,第 r 行有 r+1 个杯子,累加是 1+2+…+row 个等差,约 row² / 2
- 空间：O(row)，滚动数组只存当前行,最长就是查询行的 row+1 个杯子
易错点
面试追问把动画讲成自己的话
追问为什么可以用滚动数组,而不必存整座塔?
追问中间某个杯子的累计值超过 1,会不会影响下面的计算?
这道题到这就讲完了。动画和文字是同一套思路——别光看，关掉页面自己默写一遍。然后顺着主线继续：
最大平均值和的分组
LeetCode 813 · 中等 · 沿着 动态规划套路 继续往下推进
把这道题真正学会，再走
图解算法年卡 ¥99 /年
- ✓本题每步动画的吴师兄语音讲解（全站陆续覆盖）
- ✓小欧带 8 步通关训练——追问到不看答案也能写对、能 30 秒讲给面试官听
- ✓学习报告，记录每道题的掌握程度
76k+ GitHub Star · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题