华为 OD 训练营 · 题解精讲
LC860. 柠檬水找零
配套讲解：视频讲解 ↗
LC860. 柠檬水找零 视频地址：https://uha.xet.tech/s/3Hi5qk
题目描述
在柠檬水摊上，每一杯柠檬水的售价为 5 美元。顾客排队购买你的产品，（按账单 bills 支付的顺序）一次购买一杯。 每位顾客只买一杯柠檬水，然后向你付 5 美元、10 美元或 20 美元。 你必须给每个顾客正确找零，也就是说净交易是每位顾客向你支付 5 美元。 注意，一开始你手头没有任何零钱。 给你一个整数数组 bills ，其中 bills[i] 是第 i 位顾客付的账。如果你能给每位顾客正确找零，返回 true ，否则返回 false 。
题目解析
解题思路
本题模拟找零过程，核心是贪心策略：收到大面额钞票时，优先用大面额零钱找零，因为5元零钱更通用（既能找10元也能找20元）。用两个变量 five 和 ten 记录手中5元和10元钞票的数量（20元钞票不会用于找零，故无需记录）。
关键步骤
1. 遍历 bills 数组，对每位顾客的付款分情况处理：
- 付5元：直接收下，
five += 1。 - 付10元：必须找5元。若
five > 0，则five -= 1, ten += 1；否则返回false。 - 付20元：优先用一张10元和一张5元找零（
ten > 0 and five > 0）；若不行，再用三张5元（five >= 3）；否则返回false。
2. 遍历结束后返回 true。
找零决策树示意：
付20元时：
有10元+5元？ → 用10+5找零
否则有3张5元？ → 用三张5元找零
否则 → 失败复杂度分析
- 时间复杂度：O(N)，只需一次遍历
bills数组。 - 空间复杂度：O(1)，仅用两个整数变量记录零钱数量。
参考代码
# 登录 AlgoMooc 官网获取更多算法图解
# https:#www.algomooc.com
# 作者：程序员吴师兄
# 代码有看不懂的地方一定要私聊咨询吴师兄呀
# 柠檬水找零（ LeetCode 860 ）:https:#leetcode-cn.com/problems/lemonade-change/
class Solution:
def lemonadeChange(self, bills: List[int]) -> bool:
# 用来记录 5 元钞票的数量
five = 0
# 用来记录 10 元钞票的数量
ten = 0
# 顾客开始按顺序购买，并找零
for i in range(len(bills)) :
# 1、如果发现是 5 元面额
if bills[i] == 5 :
# 那么可以直接收钱，不需要找零
# 并且 5 元钞票的数量加 1
five += 1
# 2、如果发现是 10 元面额
elif bills[i] == 10 :
# 如果手中有 5 元钞票，则找零 5 元
if five > 0 :
# 5 元钞票的数量减 1
five -= 1
# 10 元钞票的数量加 1
ten += 1
else :
# 如果手中没有 5 元钞票，说明找零失败
return False
# 3、如果发现是 20 元面额
else :
# 如果手中有 10 元 和 5 元钞票，则找零 1 张 10 元和 1 张 5 元的钞票
if ten > 0 and five > 0 :
# 5 元钞票的数量减 1
five -= 1
# 10 元钞票的数量减 1
ten -= 1
else:
# 如果手中只有 5 元的，并且数量超过或者等于 3 张
# 那么找零 3 张 5 元的钞票
if five >= 3 :
# 5 元钞票的数量减 3
five -= 3
else :
# 说明这个时候顾客付 20 元的时候
# 1、手中没有 1 张 10 元的和 1 张 5 元的
# 2、手中没有 3 张 5 元的
# 说明找零失败
return False
# 所有顾客都找零了，成功
return True
四、复杂度分析
时间复杂度：O(N)，其中 N 是 bills 的长度。
空间复杂度：O(1)。