§1
题目描述
在柠檬水摊上,每杯柠檬水售价 5 美元。顾客按 bills 的顺序排队,每位顾客买一杯,并支付 5、10 或 20 美元。你必须给每位顾客正确找零。初始时你没有任何零钱。给你 bills,如果能给每位顾客正确找零,返回 true;否则返回 false。
输入 = bills = [5,5,5,10,20]
输出 = true
解释 = 前 3 位给了 5;第 4 位给 10,找 5;第 5 位给 20,找 10+5。
输入 = bills = [5,5,10,10,20]
输出 = false
§2
思路解析动画文字版
5 美元钞票最关键:10 美元顾客必须找 5;20 美元顾客也至少需要一个 5。
这就是贪心:局部先用掉“用途更窄”的 10,留下“用途更广”的 5。
初始化零钱盒:不需要记录 20 美元数量,因为 20 只会收进来,不会被用于找零。
第 1 位顾客付 5:5 美元正好等于价格,直接收下,零钱盒里多一张 5。
第 2 位顾客付 5:继续收 5,不用找零。现在有两张 5。
第 3 位顾客付 5:第三张 5 很重要,后面给 10 和 20 找零都要靠它。
第 4 位顾客付 10:需要找 5:收到 10 美元,要找 5 美元。如果 five == 0,就会立刻返回 false。
找零后:five=2,ten=1:给顾客找出一张 5,同时把收到的 10 放进零钱盒。
第 5 位顾客付 20:优先看 10+5:收到 20 要找 15。只要有 10 和 5,就优先用 10+5,保留更多 5 给后面的顾客。
找零后仍然成功:给出一张 10 和一张 5 后,还剩一张 5。所有顾客都正确找零。
返回 true:只要循环中从未遇到找不开的情况,就返回 true。
反例:为什么 [5,5,10,10,20] 是 false:这就是为什么五美元钞票要尽量保留;没有 5 的时候,10 再多也找不开 20。
这不是随便选一种找零方式,而是为了让后续账单更可能找开。
§3
参考代码
class Solution: def lemonadeChange(self, bills): five = 0 ten = 0 for b in bills: if b == 5: five += 1 elif b == 10: if five == 0: return False five -= 1 ten += 1 else: if ten > 0 and five > 0: ten -= 1 five -= 1 elif five >= 3: five -= 3 else: return False return True看懂代码不等于写得出。盖住上面,自己默写一遍试试。卡在哪一行说不清,就点右下角问小欧。
§4
复杂度
- 时间复杂度:O(n),每张账单只处理一次。
- 空间复杂度:O(1),只记录 5 美元和 10 美元钞票数量。
§5
易错点
✗ 错误写法:收到 20 优先用三个 5
✓ 正确写法:优先用 10+5
5 美元更通用,要尽量保留。
✗ 错误写法:收到 10 忘记检查 five
✓ 正确写法:five == 0 直接 false
10 美元顾客必须找一张 5。
✗ 错误写法:记录 20 的数量
✓ 正确写法:只记录 five 和 ten
20 不会被用来找零。
这道题到这就讲完了。动画和文字是同一套思路——别光看,关掉页面自己默写一遍。然后顺着主线继续:
下一题 · 贪心套路 4/18
→跳跃游戏 II
LeetCode 45 · 中等 · 沿着 贪心套路 继续往下推进
把这道题真正学会,再走
图解算法年卡 ¥99 /年
- ✓本题每步动画的吴师兄语音讲解(全站陆续覆盖)
- ✓小欧带 8 步通关训练——追问到不看答案也能写对、能 30 秒讲给面试官听
- ✓学习报告,记录每道题的掌握程度
299道动画图解
37节语音讲解
28课数据结构
¥0.27折合 / 天
76k+ GitHub Star · 吴师兄开源图解算法,几十万开发者在看的算法讲解
¥99 开通年卡 →
想成体系刷透这类套路?去图解算法专题