LeetCode 860. 柠檬水找零
目录
题目描述
题意分析
每杯柠檬水卖 5 元，顾客按数组给定的顺序排队，每人手里只可能是 5、10、20 三种面额之一，且每人只买一杯。你开始时身上没有任何零钱，收到的钱只能用来给后面的顾客找零。问能否给每一位顾客都正确找零。
把三种面额翻译成收支：收 5 元不用找零，净增一张 5；收 10 元要找 5 元，净增一张 10、减一张 5；收 20 元要找 15 元，只有「一张 10 加一张 5」和「三张 5」两种组合。
全题的分歧点只在收 20 元这一步——它是唯一存在选择的地方，其余两种面额的处理方式是唯一确定的。所以这道题的「算法含量」全部集中在「20 元该怎么找」，其他都是记账。
约束里账单数量最多 10 万，面额只有三种，$O(n)$ 一遍扫描是自然选择。更重要的是，钞票只按张数区分、没有编号，所以状态只需要两个整数：手里 5 元和 10 元各有多少张。20 元收进来之后永远找不出去（题目里没有比 20 更大的面额需要它），根本不用记。
边界：第一位顾客若付 10 或 20，此时手上一分钱没有，必然失败；
bills全是 5 时必然成功；只要中途有任何一次找不开就立刻返回 false，后面的顾客不必再看。
解法：贪心（维护 5/10 张数）
核心思路
先想想有没有必要搜索。收到 20 元时有两种找法，若对每个 20 都分叉，最坏是 $2^{n}$ 条路径，显然不可行。瓶颈在于我们担心「现在这样找，会不会导致后面找不开」。
关键观察：5 元是唯一的万能币，10 元的用途严格窄于 5 元。10 元只能参与「找 20」这一种场合；而 5 元既能找 10、又能三张凑 20、还能与 10 元搭配凑 20。换句话说，任何用得到 10 元的地方都能用两张 5 元替代，反过来则不成立。
由此得到贪心策略：收到 20 元时，优先用「10 + 5」，只有在没有 10 元可用时才退而用「5 + 5 + 5」。理由是这两种找法都花掉了 15 元的面值，但前者只消耗一张 5，后者消耗三张 5；既然 5 元更通用，就该尽量把它留在手里。
严格一点说，交换论证是这样：假设某个最优（可行）方案在某次收 20 时选了三张 5，而当时手上有 10 元。把这次改成「10 + 5」，手上就多了两张 5、少了一张 10。由于 10 元能做的事 5 元都能做（且两张 5 可替代一张 10），改动后的状态在后续每一步的可行性都不弱于原方案。因此优先用 10 元不会把可行解变成不可行解。
不变量：处理完前
k位顾客后，five与ten恰好等于「按上述贪心策略操作时手里 5 元和 10 元的张数」，并且这个组合是所有可行操作序列中「后续可行性最强」的一个。只要在某一步连贪心都找不开，就说明任何策略都找不开，可以直接判定失败。
解题步骤
- 初始化
five = 0、ten = 0：开局身无分文，这是题目明说的前提；不要误以为可以自带零钱。- 收到 5 元：
five++，无需找零。这是唯一能增加 5 元的途径，也是整个系统的「补给」。- 收到 10 元：必须找出一张 5。
five == 0时直接返回 false——此时无解，因为 5 元只有一种面额可以凑出 5 元的找零。否则five--、ten++。注意ten++不能忘，它是后面找 20 的关键资源。- 收到 20 元：先看
ten > 0 && five > 0，成立就ten--、five--。这个分支放在前面，正是贪心的落点：保 5 元。否则退到five >= 3，five -= 3。两者都不成立则返回 false。- 两个分支的先后顺序不能交换：若先判
five >= 3，就变成了「优先消耗三张 5」，会在后续需要找 5 元时提前枯竭。- 全部处理完返回 true：中途没有任何一次找不开，说明全程可行。
以
bills = [5, 5, 10, 10, 20]走一遍，正确答案是 false。第 1 位付 5：
five = 1，ten = 0。第 2 位付 5：
five = 2，ten = 0。第 3 位付 10：
five = 2 > 0，找出一张 5，five = 1，ten = 1。第 4 位付 10：
five = 1 > 0，再找一张 5，five = 0，ten = 2。第 5 位付 20：需要找 15。第一个分支要求
ten > 0 && five > 0，此时ten = 2但five = 0，不成立；第二个分支要求five >= 3，也不成立。返回 false。手上虽然握着两张 10 元共 20 元，却凑不出 15 这个数——这正是本题要考的「面值组合」而非「总金额」。再看贪心顺序为什么要紧：
bills = [5, 5, 5, 10, 20, 5, 10]。前三位付 5 后five = 3；第 4 位付 10，five = 2、ten = 1；第 5 位付 20，按正确策略用「10 + 5」，得five = 1、ten = 0；第 6 位付 5，five = 2；第 7 位付 10，找一张 5，five = 1，成功返回 true。若第 5 位改用三张 5，则five = 2 - 3不成立会走到 false 分支（five只有 2），当场就错判成无解；即便当时five够，多消耗两张 5 也会让第 7 位的找零更紧张。
代码实现
class Solution {
public boolean lemonadeChange(int[] bills) {
int five = 0;
int ten = 0;
for (int bill : bills) {
if (bill == 5) {
five++;
} else if (bill == 10) {
if (five == 0) {
return false;
}
five--;
ten++;
} else {
if (ten > 0 && five > 0) {
ten--;
five--;
} else if (five >= 3) {
five -= 3;
} else {
return false;
}
}
}
return true;
}
}
func lemonadeChange(bills []int) bool {
five, ten := 0, 0
for _, bill := range bills {
if bill == 5 {
five++
} else if bill == 10 {
if five == 0 {
return false
}
five--
ten++
} else {
if ten > 0 && five > 0 {
ten--
five--
} else if five >= 3 {
five -= 3
} else {
return false
}
}
}
return true
}
复杂度分析
- 时间复杂度：$O(n)$。每位顾客只被处理一次，分支里全是常数次的加减和比较，没有回溯也没有嵌套循环。
- 空间复杂度：$O(1)$。只用了
five和ten两个计数器；20 元钞票收进来后永远用不上，连记都不用记，这是把状态压到两个整数的关键。
关键点总结
- 贪心的成立要靠「资源通用性」的偏序关系：5 元能替代 10 元的一切用途，反之不行，所以优先花掉通用性差的那一种。这个思路可以迁移到一切「多面额/多规格资源分配」的题。
- 状态设计要问「哪些信息对未来有影响」。20 元不参与任何找零，果断不记；这一步想清楚，状态就从「所有钞票的多重集」坍缩成两个整数。
- 找零问题看的是面值组合而不是总金额：手握两张 10 元共 20 元，却凑不出 15 元。这是本题最反直觉、也最容易在面试中被追问的一点。
- 两个分支的判断顺序即是贪心策略本身，代码里
if (ten > 0 && five > 0)必须排在else if (five >= 3)前面，顺序一换算法就错了。- 一旦某步找不开就可以立即返回 false，不必继续——因为贪心状态是「后续可行性最强」的，它都失败说明任何方案都失败。
- 面试视角：这题代码只有十来行，考的是能不能把交换论证说清楚。被问「为什么优先用 10 元」时，答「因为 5 元更万能」还不够，要能补上「把三张 5 换成 10+5 后状态严格不弱」这句。
易错点总结
- 收 20 时先判
five >= 3：[5,5,5,10,20,5,10]中第 5 位会消耗掉三张 5（若当时够），后面付 10 的顾客找不开，返回 false，而正确答案是 true。- 收 10 时忘记
ten++：[5,10,5,20]里第 4 位本可用「10 + 5」，但ten一直是 0，只能走三张 5 的分支，five只有 1，误判为 false。- 收 10 时不判
five == 0：[10]会让five变成 -1 并返回 true，正确答案是 false。负数一旦出现，后续所有判断全部失真。- 用总金额判断能否找零：
[5,5,10,10,20]手上有 20 元总额，按总额判断会返回 true，但两张 10 元凑不出 15，正确答案是 false。- 收 20 时的第一个分支只判
ten > 0：[10,20]之类构造中若ten > 0而five == 0，five--会变成 -1，后续误判，正确应当同时要求five > 0。- 把 20 元也计入可找零的面额：
[5,20,20]中若第三位试图用收到的 20 元参与找零，逻辑上无从下手（找零只需 15），会写出乱七八糟的分支；20 元收下即沉没。- 中途找不开时不立即返回而是继续记账：
[5,10,10,20]第 3 位就该判 false，若只置一个标志位继续跑，five会变成负数，后面的分支行为不可预测。- 误以为顾客可以买多杯或钞票可以拆分：题目规定每人一杯、面额固定，若按「凑够金额即可」处理，
[5,5,10,10,20]会得到 true 的错误答案。- 假设
bills有序或可以重排：顾客顺序是固定的，把[10,5]排序成[5,10]会把必然失败的用例算成成功。- 返回值语义写反：题目问「能否给每位顾客找零」，中途失败返回 false、全程通过返回 true；把两者写反会让所有用例整体取反。
相似题目
| 题目 | 难度 | 考察点 |
|---|---|---|
| 455. 分发饼干 | 简单 | 双排序后双指针贪心，考的是「把最小的饼干给胃口最小的孩子」 |
| 122. 买卖股票的最佳时机 II | 中等 | 把总收益拆成每日差值，累加正数即可，贪心的正确性来自可拆分性 |
| 55. 跳跃游戏 | 中等 | 维护能到达的最远下标，同样是「一遍扫描 + 单一状态量」的可行性判定 |
| 376. 摆动序列 | 中等 | 只在方向翻转时计数，考的是识别「峰谷」这一局部最优信号 |
| 763. 划分字母区间 | 中等 | 先预处理每个字母的最后出现位置，再用扫描线切段 |
| 452. 用最少数量的箭引爆气球 | 中等 | 按右端点排序后贪心射箭，正确性靠「不选最小右端点必不更优」 |
| 406. 根据身高重建队列 | 中等 | 需要设计双关键字排序 + 按位插入，贪心顺序的推导比本题复杂得多 |
| 621. 任务调度器 | 中等 | 由最高频任务撑起桶结构，答案是闭式公式与任务总数取较大值 |
| 135. 分发糖果 | 困难 | 左右各扫一遍取最大值，说明单向贪心不足以同时满足两侧约束 |
| 322. 零钱兑换 | 中等 | 同为面额组合问题，但面额任意时贪心不成立，必须退回完全背包 DP |