⚡Flashcard Drill➔
NeetCode #141LC-799MediumArrays & Hashing
← Back to All Problems

#141 · #799 · Champagne Tower(香槟塔)

📌 Problem Statement & Constraints

Champagne is poured into the top glass of a tower. Each glass holds exactly 1 unit; excess spills equally into the two glasses below it. Given poured, query_row and query_glass, return how full the queried glass is (capped at 1). Constraints: 0 <= poured <= 10^9, 0 <= query_glass <= query_row <= 99.

💡 Core Algorithmic Approaches

  1. Simulate row by row, keeping only the current row's fill amounts.
  2. For each glass in the current row, the excess is max(0, amount - 1), split evenly between the two glasses below.
  3. Only rows up to query_row need to be simulated, and the row length grows by one each time.
  4. The answer is min(1, fill[query_glass]), since a glass can hold at most 1 unit.

💻 Benchmark Python3 Implementation

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 j, amount in enumerate(row):
                overflow = (amount - 1) / 2
                if overflow > 0:           # only excess spills
                    nxt[j] += overflow
                    nxt[j + 1] += overflow
            row = nxt
        return min(1.0, row[query_glass])

⚡ Complexity Deep Dive

⏱️ Time Complexity
O(query_row^2): the total number of simulated glasses is 1 + 2 + ... + query_row.
💾 Space Complexity
O(query_row) for the current row.

⚠️ Interview Pitfalls & Follow-ups

  • Spilling the entire amount instead of the excess: only amount - 1 overflows, and only when positive.
  • Spilling negative excess: (amount - 1) / 2 is negative when the glass is not full; the > 0 guard prevents negative champagne.
  • Forgetting to cap the result at 1: a glass cannot hold more than one unit.
  • Using integers: the amounts are fractional; use floats.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.
🎯 Drill This Card Now➔

🧩 Related Arrays & Hashing Problems

中文速览与面试要点

香槟塔

我们把玻璃杯摆成金字塔的形状,其中第一层有 1 个玻璃杯,第二层有 2 个,依次类推到第 100 层。从顶层的第一个玻璃杯开始倾倒一些香槟,当顶层杯子满了,任何溢出的香槟都会等量地从左右两侧流到下一层的两个杯子中。给你三个整数 poured(总杯数)、query_row 与 query_glass,返回 query_row 行第 query_glass 个玻璃杯中香槟的量(0 到 1 之间)。约束:0 ≤ poured ≤ 10^9;0 ≤ query_glass ≤ query_row ≤ 99。

核心要点

  • 逐层模拟溢出(标准解) :维护当前层的香槟量数组。对每个杯子,若量 &gt; 1,则溢出部分为 (v − 1) / 2 ,等量分给下一层的左右两个杯子。
  • 为什么只需模拟到 query_row :查询只关心第 query_row 行,后续层的量不影响答案,因此循环 query_row 次即可。
  • 结果取 min(1.0, ...) :杯中最多容纳 1 杯,因此最终答案是 min(1.0, row[query_glass]) 。
  • 为什么不会超时 :query_row ≤ 99,因此最多模拟 99 层、每层最多 100 个杯子,总操作数约 5000 次。

常见陷阱

  • 对量 ≤ 1 的杯子也计算溢出 : (v - 1) / 2 在 v ≤ 1 时为负数,会把「负香槟」传给下层,导致结果错误。必须先判断 v &gt; 1 。
  • 忘记 min(1.0, ...) : poured 很大时,目标杯子可能收到远超 1 的量,但杯中最多容纳 1,必须截断。
  • 模拟全部 100 层 :虽然不影响正确性,但多做了无用功(查询层之下的量无关)。只模拟到 query_row 即可。
  • 用整数除法 : (v - 1) // 2 会丢失精度,必须用浮点除法 / 2.0 。

参考实现

class Solution:
    def champagneTower(self, poured: int, query_row: int, query_glass: int) -> float:
        row = [float(poured)]          # 第 0 层只有 1 个杯子
        for _ in range(query_row):
            nxt = [0.0] * (len(row) + 1)
            for i, v in enumerate(row):
                if v > 1.0:            # 只有溢出的杯子才向下一层传递
                    over = (v - 1.0) / 2.0
                    nxt[i] += over     # 流向左下
                    nxt[i + 1] += over # 流向右下
            row = nxt
        return min(1.0, row[query_glass])