登录BFS 模拟 + 优化（Python/Java/C++/C/Go/JS/Rust）
类似 102. 二叉树的层序遍历，用一个 BFS 模拟香槟溢出流程：第一层溢出的香槟流到第二层，第二层溢出的香槟流到第三层，依此类推。
具体地：
- 处理第一层到第二层，从 $(0,0)$ 溢出的香槟流到 $(1,0)$ 和 $(1,1)$。设溢出的香槟量为 $x$，那么 $(1,0)$ 和 $(1,1)$ 的香槟量都增加 $\dfrac{x}{2}$。
- 处理第二层到第三层，从 $(1,0)$ 溢出的香槟流到 $(2,0)$ 和 $(2,1)$，从 $(1,1)$ 溢出的香槟流到 $(2,1)$ 和 $(2,2)$。
- 依此类推。一般地，从 $(i,j)$ 溢出的香槟流到 $(i+1,j)$ 和 $(i+1,j+1)$。设溢出的香槟量为 $x$，那么下一层的 $j$ 和 $j+1$ 的香槟量都增加 $\dfrac{x}{2}$。用一个数组保存下一层每个玻璃杯的香槟量。
优化前
###py
class Solution:
def champagneTower(self, poured: int, queryRow: int, queryGlass: int) -> float:
cur = [float(poured)]
for i in range(1, queryRow + 1):
nxt = [0.0] * (i + 1)
for j, x in enumerate(cur):
if x > 1: # 溢出到下一层
nxt[j] += (x - 1) / 2
nxt[j + 1] += (x - 1) / 2
cur = nxt
return min(cur[queryGlass], 1.0) # 如果溢出，容量是 1
###java
class Solution {
public double champagneTower(int poured, int queryRow, int queryGlass) {
double[] cur = new double[]{(double) poured};
for (int i = 1; i <= queryRow; i++) {
double[] nxt = new double[i + 1];
for (int j = 0; j < cur.length; j++) {
double x = cur[j] - 1;
if (x > 0) { // 溢出到下一层
nxt[j] += x / 2;
nxt[j + 1] += x / 2;
}
}
cur = nxt;
}
return Math.min(cur[queryGlass], 1); // 如果溢出，容量是 1
}
}
###cpp
class Solution {
public:
double champagneTower(int poured, int queryRow, int queryGlass) {
vector<double> cur = {1.0 * poured};
for (int i = 1; i <= queryRow; i++) {
vector<double> nxt(i + 1);
for (int j = 0; j < cur.size(); j++) {
double x = cur[j] - 1;
if (x > 0) { // 溢出到下一层
nxt[j] += x / 2;
nxt[j + 1] += x / 2;
}
}
cur = move(nxt);
}
return min(cur[queryGlass], 1.0); // 如果溢出，容量是 1
}
};
###c
#define MIN(a, b) ((b) < (a) ? (b) : (a))
double champagneTower(int poured, int queryRow, int queryGlass) {
double* cur = malloc(sizeof(double));
cur[0] = poured;
int curSize = 1;
for (int i = 1; i <= queryRow; i++) {
double* nxt = calloc(i + 1, sizeof(double));
for (int j = 0; j < curSize; j++) {
double x = cur[j] - 1;
if (x > 0) { // 溢出到下一层
nxt[j] += x / 2;
nxt[j + 1] += x / 2;
}
}
free(cur);
cur = nxt;
curSize = i + 1;
}
double ans = MIN(cur[queryGlass], 1); // 如果溢出，容量是 1
free(cur);
return ans;
}
###go
func champagneTower(poured, queryRow, queryGlass int) float64 {
cur := []float64{float64(poured)}
for i := 1; i <= queryRow; i++ {
nxt := make([]float64, i+1)
for j, x := range cur {
if x > 1 { // 溢出到下一层
nxt[j] += (x - 1) / 2
nxt[j+1] += (x - 1) / 2
}
}
cur = nxt
}
return min(cur[queryGlass], 1) // 如果溢出，容量是 1
}
###js
var champagneTower = function(poured, queryRow, queryGlass) {
let cur = [poured];
for (let i = 1; i <= queryRow; i++) {
const nxt = Array(i + 1).fill(0);
for (let j = 0; j < cur.length; j++) {
const x = cur[j] - 1;
if (x > 0) { // 溢出到下一层
nxt[j] += x / 2;
nxt[j + 1] += x / 2;
}
}
cur = nxt;
}
return Math.min(cur[queryGlass], 1); // 如果溢出，容量是 1
};
###rust
impl Solution {
pub fn champagne_tower(poured: i32, query_row: i32, query_glass: i32) -> f64 {
let mut cur = vec![poured as f64];
for i in 1..=query_row as usize {
let mut nxt = vec![0.0; i + 1];
for (j, x) in cur.into_iter().enumerate() {
if x > 1.0 { // 溢出到下一层
nxt[j] += (x - 1.0) / 2.0;
nxt[j + 1] += (x - 1.0) / 2.0;
}
}
cur = nxt;
}
cur[query_glass as usize].min(1.0) // 如果溢出，容量是 1
}
}
优化
无需使用两个数组，可以像 0-1 背包那样，在同一个数组上修改。
###py
class Solution:
def champagneTower(self, poured: int, queryRow: int, queryGlass: int) -> float:
f = [0.0] * (queryRow + 1)
f[0] = float(poured)
for i in range(queryRow):
for j in range(i, -1, -1):
x = f[j] - 1
if x > 0:
f[j + 1] += x / 2
f[j] = x / 2
else:
f[j] = 0.0
return min(f[queryGlass], 1.0) # 如果溢出，容量是 1
###java
class Solution {
public double champagneTower(int poured, int queryRow, int queryGlass) {
double[] f = new double[queryRow + 1];
f[0] = poured;
for (int i = 0; i < queryRow; i++) {
for (int j = i; j >= 0; j--) {
double x = f[j] - 1;
if (x > 0) {
f[j + 1] += x / 2;
f[j] = x / 2;
} else {
f[j] = 0;
}
}
}
return Math.min(f[queryGlass], 1); // 如果溢出，容量是 1
}
}
###cpp
class Solution {
public:
double champagneTower(int poured, int queryRow, int queryGlass) {
vector<double> f(queryRow + 1);
f[0] = poured;
for (int i = 0; i < queryRow; i++) {
for (int j = i; j >= 0; j--) {
double x = f[j] - 1;
if (x > 0) {
f[j + 1] += x / 2;
f[j] = x / 2;
} else {
f[j] = 0;
}
}
}
return min(f[queryGlass], 1.0); // 如果溢出，容量是 1
}
};
###c
#define MIN(a, b) ((b) < (a) ? (b) : (a))
double champagneTower(int poured, int queryRow, int queryGlass) {
double* f = calloc(queryRow + 1, sizeof(double));
f[0] = poured;
for (int i = 0; i < queryRow; i++) {
for (int j = i; j >= 0; j--) {
double x = f[j] - 1;
if (x > 0) {
f[j + 1] += x / 2;
f[j] = x / 2;
} else {
f[j] = 0;
}
}
}
double ans = MIN(f[queryGlass], 1); // 如果溢出，容量是 1
free(f);
return ans;
}
###go
func champagneTower(poured, queryRow, queryGlass int) float64 {
f := make([]float64, queryRow+1)
f[0] = float64(poured)
for i := range queryRow {
for j := i; j >= 0; j-- {
x := f[j] - 1
if x > 0 {
f[j+1] += x / 2
f[j] = x / 2
} else {
f[j] = 0
}
}
}
return min(f[queryGlass], 1) // 如果溢出，容量是 1
}
###js
var champagneTower = function(poured, queryRow, queryGlass) {
const f = Array(queryRow + 1).fill(0);
f[0] = poured;
for (let i = 0; i < queryRow; i++) {
for (let j = i; j >= 0; j--) {
const x = f[j] - 1;
if (x > 0) {
f[j + 1] += x / 2;
f[j] = x / 2;
} else {
f[j] = 0;
}
}
}
return Math.min(f[queryGlass], 1); // 如果溢出，容量是 1
};
###rust
impl Solution {
pub fn champagne_tower(poured: i32, query_row: i32, query_glass: i32) -> f64 {
let query_row = query_row as usize;
let mut f = vec![0.0; query_row + 1];
f[0] = poured as f64;
for i in 0..query_row {
for j in (0..=i).rev() {
let x = f[j] - 1.0;
if x > 0.0 {
f[j + 1] += x / 2.0;
f[j] = x / 2.0;
} else {
f[j] = 0.0;
}
}
}
f[query_glass as usize].min(1.0) // 如果溢出，容量是 1
}
}
复杂度分析
- 时间复杂度：$\mathcal{O}(\textit{queryRow}^2)$。
- 空间复杂度：$\mathcal{O}(\textit{queryRow})$。
相似题目
分类题单
- 滑动窗口与双指针（定长/不定长/单序列/双序列/三指针/分组循环）
- 二分算法（二分答案/最小化最大值/最大化最小值/第K小）
- 单调栈（基础/矩形面积/贡献法/最小字典序）
- 网格图（DFS/BFS/综合应用）
- 位运算（基础/性质/拆位/试填/恒等式/思维）
- 图论算法（DFS/BFS/拓扑排序/基环树/最短路/最小生成树/网络流）
- 动态规划（入门/背包/划分/状态机/区间/状压/数位/数据结构优化/树形/博弈/概率期望）
- 常用数据结构（前缀和/差分/栈/队列/堆/字典树/并查集/树状数组/线段树）
- 数学算法（数论/组合/概率期望/博弈/计算几何/随机算法）
- 贪心与思维（基本贪心策略/反悔/区间/字典序/数学/思维/脑筋急转弯/构造）
- 链表、树与回溯（前后指针/快慢指针/DFS/BFS/直径/LCA）
- 字符串（KMP/Z函数/Manacher/字符串哈希/AC自动机/后缀数组/子序列自动机）
欢迎关注 B站@灵茶山艾府
