香槟塔 图解题解
这道题到底在问什么
- 输入
- poured=2, row=1, glass=1
- 输出
- 0.5(顶杯溢出 1 杯,平分给下面两杯各 0.5)
- 输入
- poured=8, row=3, glass=2
- 输出
- 0.875(本动画演示的实例)
最优解：一步一步想明白
- 3记住口诀:「满 1 才溢,溢出平分给下面两杯」,下面逐杯套它。
- 4先把全部 8 杯香槟倒进顶杯:第 0 行只有 1 个杯子,里面是 8(紫)。它远远超过 1,接下来会大量溢出。其余行暂时都是空的(0)。
- 5现在看第 0 行(蓝)的每个杯子。凡是超过 1 的,多出来的部分要平分流进第 1 行紧挨它的左右两杯。第 1 行此刻还是空的,等着接香槟。
- 6看第 0 行第 0 个杯子(紫),里面有 8,超过 1。多出来的 8 - 1 = 7 平分成两份,每份 3.5,分别流向下一行第 0、第 1 个杯子。
- 7把 3.5 同时灌进第 1 行的第 0 杯和第 1 杯(绿,它们现在分别累计到 3.5 和 3.5)。同一个下层杯子可能同时接到左上、右上两个杯子的溢出,所以用累加。
- 8第 0 行所有杯子都处理过了。第 1 行现在是 [3.5, 3.5](绿)。继续往下一行递推。
- 9现在看第 1 行(蓝)的每个杯子。凡是超过 1 的,多出来的部分要平分流进第 2 行紧挨它的左右两杯。第 2 行此刻还是空的,等着接香槟。
- 10看第 1 行第 0 个杯子(紫),里面有 3.5,超过 1。多出来的 3.5 - 1 = 2.5 平分成两份,每份 1.25,分别流向下一行第 0、第 1 个杯子。
- 11把 1.25 同时灌进第 2 行的第 0 杯和第 1 杯(绿,它们现在分别累计到 1.25 和 1.25)。同一个下层杯子可能同时接到左上、右上两个杯子的溢出,所以用累加。
- 12看第 1 行第 1 个杯子(紫),里面有 3.5,超过 1。多出来的 3.5 - 1 = 2.5 平分成两份,每份 1.25,分别流向下一行第 1、第 2 个杯子。
- 13把 1.25 同时灌进第 2 行的第 1 杯和第 2 杯(绿,它们现在分别累计到 2.5 和 1.25)。同一个下层杯子可能同时接到左上、右上两个杯子的溢出,所以用累加。
- 14第 1 行所有杯子都处理过了。第 2 行现在是 [1.25, 2.5, 1.25](绿)。继续往下一行递推。
- 15现在看第 2 行(蓝)的每个杯子。凡是超过 1 的,多出来的部分要平分流进第 3 行紧挨它的左右两杯。第 3 行此刻还是空的,等着接香槟。
- 16看第 2 行第 0 个杯子(紫),里面有 1.25,超过 1。多出来的 1.25 - 1 = 0.25 平分成两份,每份 0.125,分别流向下一行第 0、第 1 个杯子。
- 17把 0.125 同时灌进第 3 行的第 0 杯和第 1 杯(绿,它们现在分别累计到 0.125 和 0.125)。同一个下层杯子可能同时接到左上、右上两个杯子的溢出,所以用累加。
- 18看第 2 行第 1 个杯子(紫),里面有 2.5,超过 1。多出来的 2.5 - 1 = 1.5 平分成两份,每份 0.75,分别流向下一行第 1、第 2 个杯子。
- 19把 0.75 同时灌进第 3 行的第 1 杯和第 2 杯(绿,它们现在分别累计到 0.875 和 0.75)。同一个下层杯子可能同时接到左上、右上两个杯子的溢出,所以用累加。
- 20看第 2 行第 2 个杯子(紫),里面有 1.25,超过 1。多出来的 1.25 - 1 = 0.25 平分成两份,每份 0.125,分别流向下一行第 2、第 3 个杯子。
- 21把 0.125 同时灌进第 3 行的第 2 杯和第 3 杯(绿,它们现在分别累计到 0.875 和 0.125)。同一个下层杯子可能同时接到左上、右上两个杯子的溢出,所以用累加。
- 22第 2 行所有杯子都处理过了。第 3 行现在是 [0.125, 0.875, 0.875, 0.125](绿)。已经推到查询的第 3 行,接下来直接读取第 2 个杯子并对 1 取 min。
- 23推到查询的第 3 行,看第 2 个杯子(紫):里面累计到 0.875。杯子最多装 1 杯,所以取 min(1, 0.875) = 0.875。这就是最终答案。
- 24回顾整条链:8 杯从顶杯一路溢下来,每层「满 1 才溢、溢出平分给下面两杯」。查询的杯子(紫)最终是 0.875。整道题的核心就是从上到下逐行模拟这一个溢出规则。
⚠️ 容易写错的地方
✗ 错：溢出量忘记除以 2
✓ 对：over = max(0, x - 1) / 2
溢出的香槟要平分给左右两个杯子,每个只得一半;不除 2 会让总量翻倍
✗ 错：下一行杯子用赋值而不是累加
✓ 对：next[i] += over; next[i+1] += over
下层一个杯子会同时接到左上、右上两个杯子的溢出,必须累加,直接赋值会丢掉其中一份
✗ 错：忘了最后对 1 取 min
✓ 对：return min(1, row[query_glass])
杯子最多装满 1 杯,中间累计值可能超过 1(它会继续往下溢),但该杯实际持有量上限是 1
完整代码（Python / C++ / Java）
Python
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])C++
#include <vector>
using namespace std;
class Solution {
public:
double champagneTower(int poured, int query_row, int query_glass) {
vector<double> row{(double)poured};
for (int r = 0; r < query_row; ++r) {
vector<double> nxt(row.size() + 1);
for (int i = 0; i < (int)row.size(); ++i) {
double over = max(0.0, row[i] - 1.0) / 2.0;
nxt[i] += over; nxt[i + 1] += over;
}
row.swap(nxt);
}
return min(1.0, row[query_glass]);
}
};Java
import java.util.*;
class Solution {
public double champagneTower(int poured, int query_row, int query_glass) {
double[] row = {poured};
for (int r = 0; r < query_row; r++) {
double[] next = new double[row.length + 1];
for (int i = 0; i < row.length; i++) {
double over = Math.max(0.0, row[i] - 1.0) / 2.0;
next[i] += over; next[i + 1] += over;
}
row = next;
}
return Math.min(1.0, row[query_glass]);
}
}复杂度
时间
O(row²)
从第 0 行推到第 query_row 行,第 r 行有 r+1 个杯子,累加是 1+2+…+row 个等差,约 row² / 2
空间
O(row)
滚动数组只存当前行,最长就是查询行的 row+1 个杯子
看不够？换成动画再走一遍
上面的推演每一步都对应一帧动画。点开交互动画版，能一步步看着 香槟塔 的数据怎么变、指针怎么走，还能切 Python / Java / C++ 跟着练。
面试官可能追问
为什么可以用滚动数组,而不必存整座塔?+
因为第 r+1 行的每个杯子只依赖第 r 行相邻两个杯子的溢出,递推时只用得到「上一行」。所以维护一个一维数组、每行算完就覆盖成下一行即可,空间从 O(row²) 降到 O(row)。如果题目要查询多次不同的行列,可以一次性把整座塔(二维)算到最深行缓存起来复用。
中间某个杯子的累计值超过 1,会不会影响下面的计算?+
不会影响下面,反而是必须的。中间累计值代表「流经这个杯子的总量」,它要先超过 1 才能继续往下溢出 (x - 1) / 2;所以模拟过程中不能提前对 1 取 min,只有在最后读取目标杯子时才取 min。把上限提前压到 1 会少算下层应得的香槟。
想听吴师兄把这道题讲给你听？
文字版和动画都随便看。开通图解算法年卡，可以听吴师兄声线把 香槟塔 一步步讲透（全站 0 节语音精讲，持续扩充）， 卡住的地方还有 AI 私教小欧就着动画帮你拆到懂。
本平台为独立第三方培训机构，与华为技术有限公司无任何关联；课程的服务内容与权益以购买协议为准，学习效果因个人情况而异。「华为 OD」「华为可信」等仅为对岗位与考试方向的客观描述，相关商标归各自权利人所有。