LeetCode 860简单贪心
柠檬水找零 图解题解
这道题到底在问什么
在柠檬水摊上，每杯柠檬水售价 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
最优解：一步一步想明白
- 35 美元钞票最关键：10 美元顾客必须找 5；20 美元顾客也至少需要一个 5。
- 4这就是贪心：局部先用掉“用途更窄”的 10，留下“用途更广”的 5。
- 5five = 0; ten = 0不需要记录 20 美元数量，因为 20 只会收进来，不会被用于找零。
- 6if b == 5: five += 15 美元正好等于价格，直接收下，零钱盒里多一张 5。
- 7if b == 5: five += 1继续收 5，不用找零。现在有两张 5。
- 8if b == 5: five += 1第三张 5 很重要，后面给 10 和 20 找零都要靠它。
- 9elif b == 10:收到 10 美元，要找 5 美元。如果 five == 0，就会立刻返回 false。
- 10five -= 1; ten += 1给顾客找出一张 5，同时把收到的 10 放进零钱盒。
- 11if ten > 0 and five > 0:收到 20 要找 15。只要有 10 和 5，就优先用 10+5，保留更多 5 给后面的顾客。
- 12ten -= 1; five -= 1给出一张 10 和一张 5 后，还剩一张 5。所有顾客都正确找零。
- 13return True只要循环中从未遇到找不开的情况，就返回 true。
- 14这就是为什么五美元钞票要尽量保留；没有 5 的时候，10 再多也找不开 20。
- 17这不是随便选一种找零方式，而是为了让后续账单更可能找开。
⚠️ 容易写错的地方
✗ 错：收到 20 优先用三个 5
✓ 对：优先用 10+5
5 美元更通用，要尽量保留。
✗ 错：收到 10 忘记检查 five
✓ 对：five == 0 直接 false
10 美元顾客必须找一张 5。
✗ 错：记录 20 的数量
✓ 对：只记录 five 和 ten
20 不会被用来找零。
完整代码（Python）
Python
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复杂度
时间复杂度
O(n)
每张账单只处理一次。
空间复杂度
O(1)
只记录 5 美元和 10 美元钞票数量。
看不够？换成动画再走一遍
上面的推演每一步都对应一帧动画。点开交互动画版，能一步步看着 柠檬水找零 的数据怎么变、指针怎么走，还能切 Python / Java / C++ 跟着练。
面试官可能追问
这道题为什么用「贪心」，换最直接的暴力解会差在哪？+
贪心抓住了本题的结构特征，把暴力解里重复的工作省掉；暴力解通常要多嵌套一层枚举，数据一大就超时。具体对比见上文「暴力解及其卡点」与「最优解逐步推演」两节。
时间复杂度为什么是 undefined？怎么推出来的？+
按上文复杂度小节的推导，时间复杂度为 undefined。
本平台为独立第三方培训机构，与华为技术有限公司无任何关联；课程的服务内容与权益以购买协议为准，学习效果因个人情况而异。「华为 OD」「华为可信」等仅为对岗位与考试方向的客观描述，相关商标归各自权利人所有。