LeetCode 题解工作台
柠檬水找零
在柠檬水摊上，每一杯柠檬水的售价为 5 美元。顾客排队购买你的产品，（按账单 bills 支付的顺序）一次购买一杯。 每位顾客只买一杯柠檬水，然后向你付 5 美元、 10 美元或 20 美元。你必须给每个顾客正确找零，也就是说净交易是每位顾客向你支付 5 美元。 注意，一开始你手头没有任何零钱。 给…
2
题型
7
代码语言
3
相关题
当前训练重点
简单 · 贪心·invariant
答案摘要
我们从前往后遍历账单数组 ，对于当前遍历到的账单： - 如果是 美元，那么直接收下即可；
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 贪心·invariant 题型思路
题目描述
在柠檬水摊上，每一杯柠檬水的售价为 5 美元。顾客排队购买你的产品，（按账单 bills 支付的顺序）一次购买一杯。
每位顾客只买一杯柠檬水，然后向你付 5 美元、10 美元或 20 美元。你必须给每个顾客正确找零，也就是说净交易是每位顾客向你支付 5 美元。
注意，一开始你手头没有任何零钱。
给你一个整数数组 bills ，其中 bills[i] 是第 i 位顾客付的账。如果你能给每位顾客正确找零，返回 true ，否则返回 false 。
示例 1：
输入：bills = [5,5,5,10,20] 输出：true 解释： 前 3 位顾客那里，我们按顺序收取 3 张 5 美元的钞票。 第 4 位顾客那里，我们收取一张 10 美元的钞票，并返还 5 美元。 第 5 位顾客那里，我们找还一张 10 美元的钞票和一张 5 美元的钞票。 由于所有客户都得到了正确的找零，所以我们输出 true。
示例 2：
输入：bills = [5,5,10,10,20] 输出：false 解释： 前 2 位顾客那里，我们按顺序收取 2 张 5 美元的钞票。 对于接下来的 2 位顾客，我们收取一张 10 美元的钞票，然后返还 5 美元。 对于最后一位顾客，我们无法退回 15 美元，因为我们现在只有两张 10 美元的钞票。 由于不是每位顾客都得到了正确的找零，所以答案是 false。
提示：
1 <= bills.length <= 105bills[i]不是5就是10或是20
解题思路
方法一：贪心 + 模拟
我们从前往后遍历账单数组 ，对于当前遍历到的账单：
- 如果是 美元，那么直接收下即可；
- 如果是 美元，那么需要找零 美元；
- 如果是 美元，那么需要找零 美元，此时有两种找零方式：找零 张 美元 + 张 美元；找零 张 美元。我们优先用第一种找零方式，如果没有足够的 美元，那么用第二种方式；
- 如果发现 美元的数量不够，直接返回
false。
遍历结束，说明我们没有遇到无法找零的情况，返回 true 即可。
时间复杂度 ，空间复杂度 。其中 为账单数组 的长度。
class Solution:
def lemonadeChange(self, bills: List[int]) -> bool:
five = ten = 0
for v in bills:
if v == 5:
five += 1
elif v == 10:
ten += 1
five -= 1
else:
if ten:
ten -= 1
five -= 1
else:
five -= 3
if five < 0:
return False
return True
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | complexity is O(n) because each bill is processed once. Space complexity is O(1) since only counters for $5 and $10 bills are maintained, independent of the input size. |
| 空间 | O(1) |
面试官常问的追问
外企场景- question_mark
Are you tracking the denominations separately to manage change?
- question_mark
Do you prefer giving larger bills first when giving change?
- question_mark
What happens if a $20 bill arrives but you cannot provide $15 in change?
常见陷阱
外企场景- error
Failing to prioritize giving a $10 and a $5 when available for a $20 bill.
- error
Not updating the counters correctly for each transaction.
- error
Assuming having any bills is sufficient without checking exact change required.
进阶变体
外企场景- arrow_right_alt
Change amounts could vary, requiring a flexible greedy approach.
- arrow_right_alt
Customers may pay with more denominations like $50, testing invariant logic.
- arrow_right_alt
Determine the minimum initial change needed to guarantee all customers can be served.