LeetCode 题解工作台
换水问题 II
给你两个整数 numBottles 和 numExchange 。 numBottles 代表你最初拥有的满水瓶数量。在一次操作中，你可以执行以下操作之一： 喝掉任意数量的满水瓶，使它们变成空水瓶。 用 numExchange 个空水瓶交换一个满水瓶。然后，将 numExchange 的值增加 1 …
2
题型
8
代码语言
3
相关题
当前训练重点
中等 · 数学·结合·模拟
答案摘要
我们可以在一开始就喝掉所有的满水瓶，因此初始时我们喝到的水数量为 。然后我们不断地进行以下操作： - 如果当前有 个空水瓶，我们就可以用它们换一瓶满水瓶，换完后， 的值增加 。然后，我们喝掉这瓶水，喝到的水数量增加 ，空水瓶数量增加 。
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 数学·结合·模拟 题型思路
题目描述
给你两个整数 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 <= 1001 <= numExchange <= 100
解题思路
方法一：模拟
我们可以在一开始就喝掉所有的满水瓶，因此初始时我们喝到的水数量为 。然后我们不断地进行以下操作：
- 如果当前有 个空水瓶，我们就可以用它们换一瓶满水瓶，换完后， 的值增加 。然后，我们喝掉这瓶水，喝到的水数量增加 ，空水瓶数量增加 。
- 如果当前没有 个空水瓶，那么我们就不能再换水了，此时我们就可以停止操作。
我们不断地进行上述操作，直到我们无法再换水为止。最终我们喝到的水的数量就是答案。
时间复杂度 ，其中 是初始的满水瓶数量。空间复杂度 。
class Solution:
def maxBottlesDrunk(self, numBottles: int, numExchange: int) -> int:
ans = numBottles
while numBottles >= numExchange:
numBottles -= numExchange
numExchange += 1
ans += 1
numBottles += 1
return ans
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | complexity is O(log(numBottles)) if tracking exchanges iteratively, since each exchange reduces empty bottles. Space complexity is O(1) because only counters for full and empty bottles are maintained. |
| 空间 | Depends on the final approach |
面试官常问的追问
外企场景- question_mark
Focus on simulating each exchange step carefully rather than jumping to a formula.
- question_mark
Check whether edge cases like numBottles < numExchange are handled correctly.
- question_mark
Watch for infinite loops if empty bottles are not reduced after exchanges.
常见陷阱
外企场景- error
Trying to combine multiple exchanges at once instead of following the iterative pattern.
- error
Forgetting to increment the total drink count after each new full bottle obtained.
- error
Neglecting the scenario when remaining empty bottles are less than numExchange, causing incorrect loops.
进阶变体
外企场景- arrow_right_alt
Change numExchange to vary at each step, testing dynamic exchange rates.
- arrow_right_alt
Introduce a limit on total exchanges allowed, requiring careful simulation.
- arrow_right_alt
Start with zero full bottles but some empty bottles to see if exchange logic triggers correctly.