860. 柠檬水找零（Lemonade Change）
频次 ★★★ · 难度 🟢 · 高频：字节
题目
柠檬水摊位，每杯 5 元。顾客排队购买，每人只买一杯，支付 5 元、10 元或 20 元。初始无零钱，判断能否正确找零。
示例：
输入: bills = [5,5,5,10,20]
输出: true
解释：前 3 位收 5 元；第 4 位收 10 元找 5 元；第 5 位收 20 元找 10+5 元
输入: bills = [5,5,10,10,20]
输出: false
解释：前 4 位后剩 2 张 10 元；第 5 位收 20 元，无法找零（没有 5 元）
思路
贪心（优先用 10 元找零）：维护 5 元和 10 元的数量。遇到 20 元需要找零 15 元时，优先用 10+5 的组合（保留 5 元的灵活性），只有没有 10 元时才用 3 张 5 元。因为 5 元是万能的（可以找 10 元和 20 元），10 元只能找 20 元。
代码
public boolean lemonadeChange(int[] bills) {
int five = 0, ten = 0;
for (int bill : bills) {
if (bill == 5) {
five++;
} else if (bill == 10) {
if (five == 0) return false;
five--;
ten++;
} else { // bill == 20
// 贪心：优先用 10+5 找零，保留 5 元的灵活性
if (ten > 0 && five > 0) {
ten--;
five--;
} else if (five >= 3) {
five -= 3;
} else {
return false;
}
}
}
return true;
}复杂度
- 时间：O(n) —— 一次遍历
- 空间：O(1)
边界条件
- 第一个人不付 5 元：立即返回 false（无零钱找）
- 全是 5 元：永远正确，返回 true
- 只有 5 元和 10 元：只需检查 5 元数量是否够
- 连续多个 20 元：快速消耗零钱，容易失败
变式
易错点
- 贪心策略的具体体现：20 元找零时优先
10+5而非3×5。这是唯一需要贪心决策的地方 - 不需要维护 20 元数量：20 元只能用于找零更大的面额，但本题最大面额就是 20，所以 20 元对后续找零无帮助，无需统计
- 5 元是最关键的资源：任何时候 5 元不够就失败，因为 5 元是找 10 元和 20 元的必要组成部分
面试追问
- 为什么贪心是对的？ 面对 20 元时，10+5 和 3×5 都能找零。但 10 元只能找 20 元，而 5 元既能找 10 元也能找 20 元，所以优先花掉 10 元（保留 5 元）是局部最优，进而全局最优
- 如果顾客可以支付 50 元？ 需要更复杂的贪心策略，通常用 DP 或回溯