LeetCode 860. 柠檬水找零
题目描述
题意分析
每杯售价 5 元，顾客按给定顺序支付 5、10 或 20 元，需要立即分别找回 0、5 或 15 元。初始没有零钱，不能调整顾客顺序，也不能先借用后面顾客的钱。
解法：贪心（维护 5/10 张数）
核心思路
[!blue]
用
five、ten记录处理完前面顾客后，手中 5 元和 10 元钞票的张数。找零最多需要 15 元，20 元钞票以后也用不上，所以无需保存它的数量；只记录手中总金额则无法判断能否凑出所需面额。收到 5 元无需找零，直接增加
five；收到 10 元必须找出一张 5 元，没有其他选择，然后把收到的 10 元记入ten。只有收到 20 元时存在选择：用一张 10 元和一张 5 元，或者三张 5 元。如果两种找法都可行，优先使用 10 元加 5 元。与使用三张 5 元相比，这样手中多留两张 5 元、少留一张 10 元。未来需要那张 10 元时，总能改用留下的两张 5 元；而单独需要 5 元时，10 元却不能拆开用。因此这个选择至少保留了原来全部可行的后续找零方式，还可能保留更多选择。
这说明贪心不会因为本次选择而丢掉可行方案。若手中既凑不出 10 元加 5 元，也凑不出三张 5 元，就没有合法的 15 元组合，可以立即返回失败；全部顾客都能处理则成功。
解题步骤
- 收到五元时增加五元数量。
- 收到十元时先检查五元是否足够，再找出一张五元并收下十元。
- 收到二十元时优先用十元加五元，否则用三张五元。
- 任意一步找不开就返回 false，全部通过则返回 true。
代码实现
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)$，两个计数器。
关键点总结
[!green]
- 保存的是面额张数，不是总金额。
- 二十元不能参与本题后续找零，无需记录其数量。
- 贪心优先保留用途更广的五元。
易错点总结
[!yellow]
- 优先花三张五元：可能过早耗尽给 10 元顾客找零所必需的面额。
- 收到十元后不增加十元计数：后续不能使用已经收到的零钱。
- 十元加五元分支只检查十元：两种面额都必须至少有一张。
- 重排顾客顺序：题目要求当前就找零，后面收到的钱不能提前使用。
转载与许可
许可
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！