LC860. 柠檬水找零

题目描述

在柠檬水摊上，每一杯柠檬水的售价为 5 美元。顾客排队购买你的产品，（按账单 bills 支付的顺序）一次购买一杯。 每位顾客只买一杯柠檬水，然后向你付 5 美元、10 美元或 20 美元。 你必须给每个顾客正确找零，也就是说净交易是每位顾客向你支付 5 美元。 注意，一开始你手头没有任何零钱。 给你一个整数数组 bills ，其中 bills[i] 是第 i 位顾客付的账。如果你能给每位顾客正确找零，返回 true ，否则返回 false 。

题目解析

题目在说什么

想象你开了一个柠檬水摊，每杯柠檬水卖 5 美元。顾客排队买，每个人只买一杯，付的钱可能是 5 美元、10 美元或 20 美元。你一开始手里一分钱都没有，所以必须用顾客付的钱来找零。比如：

• 如果顾客付 5 美元，你直接收下，不用找零。
• 如果顾客付 10 美元，你需要找给他 5 美元（因为你卖 5 美元，他多给了 5 美元）。
• 如果顾客付 20 美元，你需要找给他 15 美元（可以是一张 10 美元 + 一张 5 美元，或者三张 5 美元）。

关键点：你必须按顾客排队的顺序处理，不能跳过或调换。如果某个时刻你无法找零（比如手里没有 5 美元零钱），那就失败了，返回 false；如果所有顾客都能成功找零，返回 true。

---

思路是怎么来的

这个问题其实很像我们日常生活中的“换零钱”游戏。你一开始没有零钱，但顾客付的钱会变成你的零钱。你需要决定：收到大面额钞票时，怎么找零才能保证后面的顾客也能顺利找零？

比如，你收到一张 20 美元，你有两种找零方式：

• 用一张 10 美元 + 一张 5 美元（如果手上有的话）。
• 或者用三张 5 美元（如果手上没有 10 美元，但有很多 5 美元）。

哪种方式更好？ 答案是：优先用 10 美元 + 5 美元。为什么？因为 5 美元是最“万能”的零钱——它既能找 10 美元，也能找 20 美元。而 10 美元只能用来找 20 美元。所以，如果你手上有 10 美元，尽量先用它，把 5 美元留着，以防后面有顾客付 10 美元需要找零。

这就是“贪心”思想：每次做当前看起来最好的选择——优先用大面额零钱（10 美元）找零，把更通用的小面额（5 美元）留到后面。

所以，我们只需要用两个变量：

• five：记录手上有多少张 5 美元。
• ten：记录手上有多少张 10 美元（20 美元不会用于找零，所以不用记）。

然后按顺序处理每个顾客的付款，根据情况更新这两个变量。如果某个时刻无法找零，就返回 false。

---

代码逐步拆解

我们来看参考代码，一行一行解释它在干什么。

int five = 0;   // 一开始没有 5 美元
int ten = 0;    // 一开始没有 10 美元

为什么只记 5 和 10？ 因为 20 美元不会用来找零（没有顾客会付 25 美元或 30 美元），所以收到 20 美元后，它只是“收入”，不会变成零钱。

接下来，遍历每个顾客的付款 bills[i]：

情况 1：顾客付 5 美元

if(bills[i] == 5){
    five++;   // 直接收下，5 美元数量 +1
}

解释：不用找零，所以只增加 five。

情况 2：顾客付 10 美元

else if(bills[i] == 10){
    if(five > 0){          // 检查有没有 5 美元可以找零
        five--;            // 用掉一张 5 美元
        ten++;             // 收下这张 10 美元，所以 ten 增加
    } else {
        return false;      // 没有 5 美元，找零失败
    }
}

解释：付 10 美元需要找 5 美元，所以必须有一张 5 美元。如果有，就用掉它，同时收下 10 美元（ten++）。如果没有，直接失败。

情况 3：顾客付 20 美元

else {   // bills[i] == 20
    // 优先用一张 10 美元 + 一张 5 美元
    if(ten > 0 && five > 0){
        five--;    // 用掉一张 5 美元
        ten--;     // 用掉一张 10 美元
    } 
    // 如果没有 10 美元，就用三张 5 美元
    else if(five >= 3){
        five -= 3; // 用掉三张 5 美元
    } 
    // 两种方式都不行，失败
    else {
        return false;
    }
}

解释：付 20 美元需要找 15 美元。有两种找法：