Medium

题目描述

给你两个整数 numBottles 和 numExchange。

numBottles 表示你最初拥有的满水瓶数量。在一次操作中，你可以执行以下操作之一：

  • 喝掉任意数量的满水瓶，将它们变成空瓶。
  • 用 numExchange 个空瓶换取一个满水瓶。然后，将 numExchange 的值增加 1。

注意，你不能为相同的 numExchange 值交换多批空瓶。例如，如果 numBottles == 3 且 numExchange == 1，你不能用 3 个空水瓶换取 3 个满瓶。

返回你最多能喝到的水瓶数量。

示例 1：

输入：numBottles = 13, numExchange = 6
输出：15
解释：上表显示了满水瓶数量、空水瓶数量、numExchange 的值以及喝掉的瓶数。

示例 2：

输入：numBottles = 10, numExchange = 3
输出：13
解释：上表显示了满水瓶数量、空水瓶数量、numExchange 的值以及喝掉的瓶数。

约束条件：

  • 1 <= numBottles <= 100
  • 1 <= numExchange <= 100

解题思路

这道题要求我们模拟水瓶的饮用和交换过程。关键理解题目中的两个操作：

  1. 喝掉满水瓶，变成空瓶
  2. 用一定数量的空瓶换满水瓶，且每次交换后所需空瓶数量增加1

解题思路：

贪心策略是最优的：每次当空瓶数量达到当前交换要求时，立即进行交换。这样可以最大化我们能喝到的水瓶数量。

具体步骤：

  1. 首先喝掉所有初始的满水瓶，获得相应数量的空瓶
  2. 当空瓶数量 >= 当前所需交换数量时，进行一次交换：
    • 用掉对应数量的空瓶
    • 获得1个满水瓶并立即喝掉
    • 净增加1个空瓶（喝掉获得的满水瓶）
    • 下次交换所需空瓶数量增加1
  3. 重复步骤2直到空瓶不足以进行交换

时间复杂度分析：由于每次交换所需空瓶数递增，最多进行O(√numBottles)次交换，因此算法效率很高。

推荐解法： 贪心模拟法（唯一解法）

代码实现

class Solution {
public:
    int maxBottlesDrunk(int numBottles, int numExchange) {
        int drunk = numBottles;  // 已喝的瓶子数
        int empty = numBottles;  // 空瓶数量
        
        while (empty >= numExchange) {
            empty -= numExchange;  // 用掉numExchange个空瓶
            empty += 1;            // 换来的满瓶喝掉后变成1个空瓶
            drunk += 1;            // 喝掉换来的1个满瓶
            numExchange += 1;      // 下次交换需要的空瓶数增加1
        }
        
        return drunk;
    }
};

class Solution:
    def maxBottlesDrunk(self, numBottles: int, numExchange: int) -> int:
        drunk = numBottles  # 已喝的瓶子数
        empty = numBottles  # 空瓶数量
        
        while empty >= numExchange:
            empty -= numExchange  # 用掉numExchange个空瓶
            empty += 1            # 换来的满瓶喝掉后变成1个空瓶
            drunk += 1            # 喝掉换来的1个满瓶
            numExchange += 1      # 下次交换需要的空瓶数增加1
        
        return drunk

public class Solution {
    public int MaxBottlesDrunk(int numBottles, int numExchange) {
        int drunk = numBottles;  // 已喝的瓶子数
        int empty = numBottles;  // 空瓶数量
        
        while (empty >= numExchange) {
            empty -= numExchange;  // 用掉numExchange个空瓶
            empty += 1;            // 换来的满瓶喝掉后变成1个空瓶
            drunk += 1;            // 喝掉换来的1个满瓶
            numExchange += 1;      // 下次交换需要的空瓶数增加1
        }
        
        return drunk;
    }
}

/**
 * @param {number} numBottles
 * @param {number} numExchange
 * @return {number}
 */
var maxBottlesDrunk = function(numBottles, numExchange) {
    let drunk = numBottles;  // 已喝的瓶子数
    let empty = numBottles;  // 空瓶数量
    
    while (empty >= numExchange) {
        empty -= numExchange;  // 用掉numExchange个空瓶
        empty += 1;            // 换来的满瓶喝掉后变成1个空瓶
        drunk += 1;            // 喝掉换来的1个满瓶
        numExchange += 1;      // 下次交换需要的空瓶数增加1
    }
    
    return drunk;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度说明
时间复杂度O(√numBottles)每次交换所需空瓶数递增，最多进行约√numBottles次交换
空间复杂度O(1)只使用常数个额外变量

相关题目