香槟塔 图解题解

查询那一杯，最终接住多少香槟

香槟从最顶端杯子倒进去，总量 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。

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]);
    }
}