Medium

题目描述

我们把玻璃杯摆成金字塔的形状，其中第一层有1个玻璃杯，第二层有2个玻璃杯，依此类推到第100层，每个玻璃杯都能装一杯香槟。

然后，一些香槟被倒在最顶层的玻璃杯中。当顶层的玻璃杯满了时，任何溢出的液体都会等量地流向紧挨着它左边和右边的玻璃杯。当这些玻璃杯也满了时，任何溢出的香槟都会等量地流向这些玻璃杯的左边和右边的玻璃杯，依此类推。（处于底层的玻璃杯的任何溢出的香槟都会流到地板上。）

例如，在倒了一杯香槟后，最顶层的玻璃杯满了。倒了两杯香槟后，第二层的两个玻璃杯各自盛放一半的香槟。在倒了三杯香槟后，第二层的香槟满了，此时总共有3个满的玻璃杯。在倒了四杯香槟后，第三层中间的玻璃杯半满，两边的玻璃杯各自盛放四分之一的香槟。

现在当倾倒了非负整数杯香槟后，返回第 i 行 j 个玻璃杯所盛放的香槟比例（ i 和 j 都从0开始）。

示例 1:

输入: poured = 1, query_row = 1, query_glass = 1
输出: 0.00000
解释: 我们在顶层（下标是(0,0)）倒了一杯香槟后，没有溢出，因此所有在顶层以下的玻璃杯都是空的。

示例 2:

输入: poured = 2, query_row = 1, query_glass = 1
输出: 0.50000
解释: 我们在顶层（下标是(0,0)）倒了两杯香槟后，有一杯量的液体溢出。下标为 (1,0) 的玻璃杯和下标为 (1,1) 的玻璃杯平分了这一杯液体，所以每个玻璃杯有一半的液体。

示例 3:

输入: poured = 100000009, query_row = 33, query_glass = 17
输出: 1.00000

提示:

  • 0 <= poured <= 10^9
  • 0 <= query_glass <= query_row < 100

解题思路

这是一道经典的动态规划问题，关键是模拟香槟从上往下流动的过程。

思路分析：

我们可以使用二维数组 dp[i][j] 表示第 i 行第 j 个玻璃杯中实际倒入的香槟量（可能超过1杯）。

算法流程：

  1. 初始化：第0行第0个杯子倒入所有香槟，即 dp[0][0] = poured
  2. 逐层计算：对于每个杯子，如果其中的香槟量超过1，则将多余部分平均分给下一层的相邻两个杯子
  3. 状态转移：如果 dp[i][j] > 1，则向 dp[i+1][j] 和 dp[i+1][j+1] 各流出 (dp[i][j] - 1) / 2
  4. 最终答案：min(1.0, dp[query_row][query_glass])

优化思路：

  • 空间优化：由于每层只依赖上一层，可以用滚动数组优化空间复杂度
  • 剪枝：当某一层所有杯子都为空时，可以提前结束

这个算法的核心思想是模拟物理过程，通过动态规划记录每个位置的状态，最终得到查询位置的结果。

代码实现

class Solution {
public:
    double champagneTower(int poured, int query_row, int query_glass) {
        vector<double> dp(101, 0.0);
        dp[0] = poured;
        
        for (int row = 0; row < query_row; row++) {
            vector<double> next(101, 0.0);
            for (int col = 0; col <= row; col++) {
                if (dp[col] > 1.0) {
                    double overflow = (dp[col] - 1.0) / 2.0;
                    next[col] += overflow;
                    next[col + 1] += overflow;
                }
            }
            dp = next;
        }
        
        return min(1.0, dp[query_glass]);
    }
};

class Solution:
    def champagneTower(self, poured: int, query_row: int, query_glass: int) -> float:
        dp = [0.0] * 101
        dp[0] = poured
        
        for row in range(query_row):
            next_dp = [0.0] * 101
            for col in range(row + 1):
                if dp[col] > 1.0:
                    overflow = (dp[col] - 1.0) / 2.0
                    next_dp[col] += overflow
                    next_dp[col + 1] += overflow
            dp = next_dp
        
        return min(1.0, dp[query_glass])

public class Solution {
    public double ChampagneTower(int poured, int query_row, int query_glass) {
        double[] dp = new double[101];
        dp[0] = poured;
        
        for (int row = 0; row < query_row; row++) {
            double[] next = new double[101];
            for (int col = 0; col <= row; col++) {
                if (dp[col] > 1.0) {
                    double overflow = (dp[col] - 1.0) / 2.0;
                    next[col] += overflow;
                    next[col + 1] += overflow;
                }
            }
            dp = next;
        }
        
        return Math.Min(1.0, dp[query_glass]);
    }
}

var champagneTower = function(poured, query_row, query_glass) {
    let dp = new Array(101).fill(0.0);
    dp[0] = poured;
    
    for (let row = 0; row < query_row; row++) {
        let next = new Array(101).fill(0.0);
        for (let col = 0; col <= row; col++) {
            if (dp[col] > 1.0) {
                let overflow = (dp[col] - 1.0) / 2.0;
                next[col] += overflow;
                next[col + 1] += overflow;
            }
        }
        dp = next;
    }
    
    return Math.min(1.0, dp[query_glass]);
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度分析
时间复杂度O(query_row²)
空间复杂度O(query_row)

说明：

  • 时间复杂度：需要遍历前 query_row 行，每行最多有 query_row + 1 个杯子
  • 空间复杂度：使用滚动数组优化，只需要 O(query_row) 的额外空间

相关题目