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
- Simulate row by row, keeping only the current row's fill amounts.
- For each glass in the current row, the excess is
max(0, amount - 1), split evenly between the two glasses below. - Only rows up to
query_rowneed to be simulated, and the row length grows by one each time. - 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 - 1overflows, and only when positive. - Spilling negative excess:
(amount - 1) / 2is negative when the glass is not full; the> 0guard 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.
🧩 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。
核心要点
- 逐层模拟溢出(标准解) :维护当前层的香槟量数组。对每个杯子,若量 > 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 > 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])