LeetCode 1518. 换水问题
目录
题目描述
题意分析
一开始有
numBottles瓶满水。喝完一瓶就得到一个空瓶，每numExchange个空瓶可以换回一瓶满水（换完之后那些空瓶就没了，换回来的满水喝完又会产生一个新空瓶）。问最多能喝到多少瓶水。
有两个容易读错的地方。第一，兑换是有找零的：如果手上有 7 个空瓶、
numExchange = 3，那么只能换 2 瓶（用掉 6 个空瓶），剩下 1 个空瓶要留到下一轮继续攒，不能丢弃。第二，换回来的水喝完还会再产生空瓶，所以这是一个会持续若干轮的连锁过程，不是「换一次就结束」。
约束里
1 <= numBottles <= 100、2 <= numExchange <= 100。numExchange >= 2是一条至关重要的保证——如果允许numExchange == 1，那么一个空瓶就能换一瓶水，可以无限喝下去，循环永不终止。题目把它排除掉了，这也意味着每一轮之后满瓶数至少减半，过程必然收敛。规模只有 100，任何写法都能过；这题真正在考的是能不能把一个带找零的连锁兑换过程用最少的状态描述清楚。
边界：
numBottles < numExchange时一轮都换不了，答案就是numBottles；numBottles恰好是numExchange的倍数时最后一轮会把空瓶用光；numExchange很大（如 100）而numBottles很小时不会进入第二轮。
解法：按轮模拟喝水和兑换
核心思路
最笨的写法是「一瓶一瓶地喝」：每喝一瓶就
empty++，然后检查empty >= numExchange就换一瓶。这当然正确，但循环次数等于最终答案（可能上千次），而且每次都要做一次判断。
观察这个过程能发现：手上有多少瓶满水，就一定会全部喝掉，不需要一瓶一瓶决策。因为喝水没有任何代价，也不存在「留着不喝更划算」的情形。既然如此，就可以成批处理——把当前所有满瓶一次性喝完，一次性转成空瓶，再一次性兑换。这样每一轮就是一次批量操作，轮数从「答案的量级」降到了对数级。
于是把状态压到最小：只需要两个变量，
numBottles表示当前手上还没喝的满瓶数，empty表示当前累计的空瓶数（含上一轮兑换后剩下的找零）。答案answer累计已喝总量。
每一轮做三件事，并且顺序固定：
- 把手上的满瓶全喝掉：
answer += numBottles，同时empty += numBottles（喝一瓶产生一个空瓶）。- 用空瓶兑换：能换
empty / numExchange瓶新的满水，这就是下一轮的numBottles。- 处理找零：兑换后剩下
empty % numExchange个空瓶，留给下一轮。
循环不变量是：每轮开始时，
numBottles是尚未饮用的满瓶数，empty是已经攒下但还不够兑换（或刚兑换完剩余）的空瓶数，answer是到目前为止已喝掉的总瓶数。当某轮兑换后numBottles变成 0，说明空瓶不足以再换一瓶，过程终止。
终止性由
numExchange >= 2保证：新的满瓶数不超过(旧满瓶数 + 旧空瓶数) / 2，而旧空瓶数小于numExchange，所以规模严格递减，最多约 $\log_2$ 轮就归零。
值得一提的还有闭式解：整个过程中，每「消耗」
numExchange - 1个净空瓶就能多喝一瓶（因为换回的一瓶喝完又还回一个空瓶，净消耗是numExchange - 1），所以答案等于numBottles + (numBottles - 1) / (numExchange - 1)。它是 $O(1)$ 的，面试时作为「还能不能更快」的回答很漂亮；但模拟写法更直白、更不容易在推导上翻车，所以主解法保留模拟，闭式解作为加分补充。
解题步骤
- 初始化
answer = 0、empty = 0：一开始还没喝过水，也没有空瓶。numBottles直接复用入参作为「当前满瓶数」，省一个变量。- 循环条件用
numBottles > 0：只要还有满水就继续。用满瓶数而不是空瓶数作条件，是因为「有满水必然会喝，喝了才会产生新空瓶」，满瓶数为 0 就意味着连锁彻底停止。- 先累加答案再转空瓶：
answer += numBottles与empty += numBottles两行都基于同一个「本轮喝掉的数量」，必须在numBottles被覆盖之前执行。- 兑换：
numBottles = empty / numExchange：整数除法自动完成「只能换整瓶」的语义，不需要额外判断够不够。- 找零：
empty %= numExchange：这一行必须在兑换之后、且必须保留余数。丢掉余数会让后续少换若干瓶，是本题最常见的错误。注意两行的先后——先用empty算出numBottles，再把empty更新为余数；顺序反了numBottles就会用被截断过的空瓶数来算。- 循环退出后返回
answer。
以
numBottles = 9、numExchange = 3走一遍（期望答案 13）。
初始：
numBottles = 9，empty = 0，answer = 0。
第 1 轮：喝掉 9 瓶，
answer = 9，empty = 0 + 9 = 9。兑换9 / 3 = 3瓶，numBottles = 3；找零9 % 3 = 0，empty = 0。
第 2 轮：喝掉 3 瓶，
answer = 12，empty = 0 + 3 = 3。兑换3 / 3 = 1瓶，numBottles = 1；找零3 % 3 = 0，empty = 0。
第 3 轮：喝掉 1 瓶，
answer = 13，empty = 0 + 1 = 1。兑换1 / 3 = 0瓶，numBottles = 0；找零1 % 3 = 1，empty = 1。
numBottles == 0，循环退出，返回 13。最后手里还剩 1 个空瓶，不够换，正确地被留下不用。
再用
numBottles = 15、numExchange = 4检验找零的必要性（期望答案 19）：
第 1 轮喝 15，answer = 15，empty = 15；换15/4 = 3瓶，找零15 % 4 = 3。
第 2 轮喝 3，answer = 18，empty = 3 + 3 = 6；换6/4 = 1瓶，找零6 % 4 = 2。
第 3 轮喝 1，answer = 19，empty = 2 + 1 = 3；换3/4 = 0瓶，结束。
返回 19。若第 1 轮把找零的 3 个空瓶丢掉（写成empty = 0），第 2 轮的empty只有 3、仍不足 4，第 3 轮就换不出那一瓶，最终返回 18，少一瓶。
顺便用闭式解核对：
15 + (15 - 1) / (4 - 1) = 15 + 4 = 19，一致。
代码实现
class Solution {
public int numWaterBottles(int numBottles, int numExchange) {
int answer = 0;
// empty 含上一轮兑换后剩下的找零，不能丢弃。
int empty = 0;
// 有满水就一定会喝，用满瓶数作为终止条件。
while (numBottles > 0) {
// 两行都基于本轮的满瓶数，必须在覆盖 numBottles 之前执行。
answer += numBottles;
empty += numBottles;
// 整数除法天然表达「只能换整瓶」。
numBottles = empty / numExchange;
// 先算兑换再取余，顺序反了会用被截断的空瓶数去换。
empty %= numExchange;
}
return answer;
}
}
func numWaterBottles(numBottles int, numExchange int) int {
answer := 0
// empty 含上一轮兑换后剩下的找零，不能丢弃。
empty := 0
// 有满水就一定会喝，用满瓶数作为终止条件。
for numBottles > 0 {
// 两行都基于本轮的满瓶数，必须在覆盖 numBottles 之前执行。
answer += numBottles
empty += numBottles
// 整数除法天然表达「只能换整瓶」。
numBottles = empty / numExchange
// 先算兑换再取余，顺序反了会用被截断的空瓶数去换。
empty %= numExchange
}
return answer
}
复杂度分析
- 时间复杂度：$O(\log_{numExchange} numBottles)$。每一轮结束后满瓶数至多变成
(本轮满瓶 + 不足一次兑换的余数) / numExchange，由于numExchange >= 2，规模至少减半，所以轮数是对数级。numBottles <= 100时最多七八轮。相比「一瓶一瓶喝」的 $O(answer)$，批量处理把循环次数从线性降到了对数。- 空间复杂度：$O(1)$。只用了
answer和empty两个整数（numBottles复用入参），与输入规模无关。若改用闭式解numBottles + (numBottles - 1) / (numExchange - 1)，时间还能降到 $O(1)$，空间同样是 $O(1)$。
关键点总结
- 能批量处理就不要逐个模拟。「手上的满水一定会全喝掉」这个判断，把每轮的循环从「喝一瓶判断一次」压缩成「一次算完」，轮数从线性降到对数。凡是模拟题，先问一句「这一步能不能成批做」。
- 整数除法与取模是「兑换 + 找零」的天然表达：
empty / numExchange是换到的瓶数，empty % numExchange是剩下的空瓶。两者必须成对出现且顺序固定，先除后模。- 状态要压到最小。本题只需「未喝的满瓶数」和「累计空瓶数」两个量，多维护任何东西（比如「已换过几轮」「历史空瓶总数」）都只会增加不同步的风险。
- 终止性来自约束
numExchange >= 2。面试时主动指出「如果numExchange可以是 1，这个循环不会停」，是很能体现严谨性的一句话。- 知道闭式解
numBottles + (numBottles - 1) / (numExchange - 1)，并能解释「每多喝一瓶净消耗numExchange - 1个空瓶」。被追问「能不能 $O(1)$」时这就是答案，也是这道简单题唯一的深度所在。- 找零绝不能丢。这是「带余数的连锁过程」类题目的共同陷阱，跨轮累积的余数往往正好凑出最后一次兑换。
易错点总结
- 兑换后把余数清零（写成
empty = 0）：numBottles = 15、numExchange = 4时第 1 轮丢掉 3 个空瓶，最终返回 18 而正确答案是 19。- 先取模再算兑换（两行顺序颠倒）：
empty先被截断成余数，再拿它去除以numExchange必然得 0，循环第一轮就退出，numBottles = 9、numExchange = 3返回 9 而不是 13。- 在
numBottles被覆盖之后才累加答案：answer += numBottles加的是新一轮换到的瓶数而非本轮喝掉的，9 / 3的用例会返回 4（3+1+0）而不是 13。- 忘记
empty += numBottles：喝掉的水没有转成空瓶，永远换不到新水，返回值恒等于初始的numBottles。- 循环条件写成
empty >= numExchange：初始empty = 0时一次都不进循环，直接返回answer = 0，连第一批满水都没喝。- 循环条件写成
numBottles >= numExchange：numBottles = 9、numExchange = 3时第 3 轮numBottles = 1 < 3就退出，那最后 1 瓶水没被喝到，返回 12 而不是 13。终止条件必须是「没有满水」而不是「不够兑换」。- 闭式解写成
numBottles + numBottles / (numExchange - 1)（分子漏减 1）：numBottles = 9、numExchange = 3得9 + 4 = 13侥幸正确，但numBottles = 4、numExchange = 2得4 + 4 = 8，正确答案是 7，恰好在整除边界上出错。- 误以为每轮只能兑换一瓶：写成
if (empty >= numExchange) { numBottles = 1; empty -= numExchange; }，numBottles = 9、numExchange = 3会退化成一轮换一瓶的低效流程，虽然多轮后结果仍可能正确，但一旦配上「一瓶一瓶喝」的写法就会因为答案累加时机错乱而出错。- 把「一瓶一瓶喝」的写法和「批量兑换」的写法混在一起：
answer在两处被累加，返回值翻倍。- 没有考虑
numExchange == 1的假设性输入：题目保证不会出现，但若把这段代码复用到没有该约束的场景，empty / 1永远等于empty，循环永不终止直接挂死。
相似题目
| 题目 | 难度 | 考察点 |
|---|---|---|
| 258. 各位相加 | 简单 | 同为「反复迭代直到收敛」的过程，且同样存在 $O(1)$ 的闭式解（数根公式） |
| 172. 阶乘后的零 | 中等 | 也是不断除以基数并累加商，考察把计数问题转化为整除链 |
| 66. 加一 | 简单 | 进位是另一种「带余数的连锁传播」，重点在全 9 时的扩容边界 |
| 874. 模拟行走机器人 | 中等 | 状态是位置与朝向，考察如何把指令流翻译成最小状态集合 |
| 1041. 困于环中的机器人 | 中等 | 只需模拟一轮就能靠周期性判定长期行为，是「找规律替代长模拟」的典型 |
| 38. 外观数列 | 中等 | 逐轮由上一轮结果生成下一轮，重点在分段计数与字符串构造 |