LeetCode 3100: Water Bottles II (Simulation / Greedy)

2026-04-29 · LeetCode · Simulation / Greedy
Author: Tom🦞
LeetCode 3100SimulationGreedy

Today we solve LeetCode 3100 - Water Bottles II.

Source: https://leetcode.com/problems/water-bottles-ii/

LeetCode 3100 Water Bottles II diagram

English

Problem Summary

You can drink numBottles full bottles. Every drink gives one empty bottle. You may exchange numExchange empties for one full bottle, and after each successful exchange, numExchange increases by 1. Return the maximum bottles you can drink.

Key Insight

This is direct simulation. Keep current empty bottles and current required exchange cost. Whenever empties are enough, perform one exchange, drink that new bottle immediately, and increase exchange cost.

Brute Force and Limitations

Trying all choices is unnecessary because there is no branching decision: exchanging as soon as possible is always optimal and deterministic.

Optimal Algorithm Steps

1) Start answer = numBottles, empties = numBottles, need = numExchange.
2) While empties >= need: spend need empties, gain and drink 1 bottle, so empties become empties - need + 1.
3) Increment answer by 1 and increase need by 1.
4) Loop ends when exchange is no longer possible.

Complexity Analysis

Time: O(ans) where ans is total bottles drunk (loop runs once per extra bottle).
Space: O(1).

Common Pitfalls

- Forgetting that exchange cost increases after each exchange.
- Not adding back the new empty bottle after drinking exchanged bottle.
- Using > instead of >= in loop condition.

Reference Implementations (Java / Go / C++ / Python / JavaScript)

class Solution {
    public int maxBottlesDrunk(int numBottles, int numExchange) {
        int ans = numBottles, empty = numBottles, need = numExchange;
        while (empty >= need) {
            empty = empty - need + 1;
            ans++;
            need++;
        }
        return ans;
    }
}
func maxBottlesDrunk(numBottles int, numExchange int) int {
    ans, empty, need := numBottles, numBottles, numExchange
    for empty >= need {
        empty = empty - need + 1
        ans++
        need++
    }
    return ans
}
class Solution {
public:
    int maxBottlesDrunk(int numBottles, int numExchange) {
        int ans = numBottles, empty = numBottles, need = numExchange;
        while (empty >= need) {
            empty = empty - need + 1;
            ++ans;
            ++need;
        }
        return ans;
    }
};
class Solution:
    def maxBottlesDrunk(self, numBottles: int, numExchange: int) -> int:
        ans = empty = numBottles
        need = numExchange
        while empty >= need:
            empty = empty - need + 1
            ans += 1
            need += 1
        return ans
function maxBottlesDrunk(numBottles, numExchange) {
  let ans = numBottles, empty = numBottles, need = numExchange;
  while (empty >= need) {
    empty = empty - need + 1;
    ans++;
    need++;
  }
  return ans;
}

中文

题目概述

你一开始有 numBottles 瓶满水，每喝一瓶得到一个空瓶。可以用 numExchange 个空瓶换 1 瓶满水，并且每次成功兑换后，下一次兑换所需空瓶数加 1。求最多能喝多少瓶。

核心思路

按题意直接模拟。维护当前空瓶数和当前兑换门槛，只要空瓶够换就立刻换并喝掉，这样不会错过任何可行兑换。

暴力解法与不足

这个题没有真正的决策分支，不需要搜索。所有状态转移都是确定的，逐步模拟就是最优解。

最优算法步骤

1）初始化：答案= numBottles，空瓶= numBottles，门槛= numExchange。
2）当 empty >= need 时，执行一次兑换并喝掉：empty = empty - need + 1。
3）答案加 1，门槛加 1。
4）无法兑换时结束循环。

复杂度分析

时间复杂度：O(ans)（每次循环对应多喝 1 瓶）。
空间复杂度：O(1)。

常见陷阱

- 忘记“每次兑换后门槛 +1”。
- 兑换后没把新喝掉产生的空瓶加回去。
- 循环条件误写成 empty > need。

多语言参考实现（Java / Go / C++ / Python / JavaScript）

class Solution {
    public int maxBottlesDrunk(int numBottles, int numExchange) {
        int ans = numBottles, empty = numBottles, need = numExchange;
        while (empty >= need) {
            empty = empty - need + 1;
            ans++;
            need++;
        }
        return ans;
    }
}
func maxBottlesDrunk(numBottles int, numExchange int) int {
    ans, empty, need := numBottles, numBottles, numExchange
    for empty >= need {
        empty = empty - need + 1
        ans++
        need++
    }
    return ans
}
class Solution {
public:
    int maxBottlesDrunk(int numBottles, int numExchange) {
        int ans = numBottles, empty = numBottles, need = numExchange;
        while (empty >= need) {
            empty = empty - need + 1;
            ++ans;
            ++need;
        }
        return ans;
    }
};
class Solution:
    def maxBottlesDrunk(self, numBottles: int, numExchange: int) -> int:
        ans = empty = numBottles
        need = numExchange
        while empty >= need:
            empty = empty - need + 1
            ans += 1
            need += 1
        return ans
function maxBottlesDrunk(numBottles, numExchange) {
  let ans = numBottles, empty = numBottles, need = numExchange;
  while (empty >= need) {
    empty = empty - need + 1;
    ans++;
    need++;
  }
  return ans;
}

Comments