柠檬水找零如何用贪心处理？（LeetCode 860）

简化版

柠檬水每杯 5 元，顾客依次用 5、10 或 20 元付款（bills[]），你初始没有零钱，要给每个顾客正确找零。问能否给所有人找开。贪心策略：维护手上 5 元和 10 元的张数，收 20 找零时优先用「一张 10 + 一张 5」，不够再用「三张 5」——因为 5 元是最灵活的通用零钱，要尽量留着。收 5 不找、收 10 找一张 5。

详细版

boolean lemonadeChange(int[] bills) {
    int five = 0, ten = 0;         // 手上 5 元、10 元的张数（20 元留不住，不用记）
    for (int b : bills) {
        if (b == 5) {
            five++;                          // 收 5，不用找
        } else if (b == 10) {
            if (five == 0) return false;     // 找 5，没有则失败
            five--; ten++;
        } else { // b == 20，要找 15
            if (ten > 0 && five > 0) {       // 优先 10 + 5
                ten--; five--;
            } else if (five >= 3) {          // 否则 3 张 5
                five -= 3;
            } else {
                return false;                // 都凑不出 15
            }
        }
    }
    return true;
}

只需记 5 和 10 的张数：20 元找不出去（没人给你找 20），存着没用，不必统计。
找 15 的贪心：优先「10+5」，把 5 元这种万能零钱尽量省下来。
复杂度：O(n) 时间、O(1) 空间。

完整版教学

一、题目本质是「零钱够不够 + 怎么找最优」

每杯 5 元，付款只有三种面额，找零情形也就固定几种：

付 5：正好，不找零，手上多一张 5。
付 10：要找回 5 元 → 消耗一张 5。
付 20：要找回 15 元 → 要么「10+5」，要么「5+5+5」。

问题就变成：收款过程中零钱能不能一直周转得开。这是个贪心 + 模拟题。

二、贪心点：找 15 时优先用 10，省下 5

唯一有「选择」的地方是收到 20 元、要找 15时：可以用 一张10 + 一张5，也可以用 三张5。两种都找出 15，选哪个？

贪心策略：优先「10+5」。 理由：5 元是最灵活的零钱——找 10 元要用 5，找 20 元也要用 5，而 10 元只能在「找 20」时派一次用场。所以要尽量保留 5 元，能用 10 元顶掉的就别动 5 元的库存。只有当手上没有 10 元时，才被迫拆三张 5。

三、交换论证：为什么优先用 10 不会更差

用交换论证验证贪心正确：假设某个最优找零序列在某次「找 15」时用了 三张5，而当时手上其实有 10 元可用。我们把这次改成「10+5」，则多留下了两张 5、少留一张 10。因为 5 元的用途严格覆盖 10 元（凡是 10 元能找的场合，5 元组合也能找；反之不然），多留 5 元、少留 10 元只会让后续更容易找零，不会更差。所以「优先用 10」总是不劣于「优先拆 5」——贪心成立。

四、为什么不用记 20 元的数量

收进来的 20 元，永远找不出去——顾客只会付 5/10/20，你从不需要「找 20 元」给别人。所以 20 元是「只进不出」的死钱，记它没有意义，代码里只维护 five 和 ten 两个计数即可。这是本题一个容易被忽略的简化点。

五、边界与陷阱

第一位顾客付 10 或 20：手上没零钱，直接 false。代码里 five==0 return false 和 20 的两个分支都覆盖了。
陷阱：找 15 时判断顺序。必须先判「10+5」再判「3 张 5」。若反过来先拆 5，会过早耗尽 5 元库存，后面遇到付 10 的顾客就找不开——这正是贪心策略要避免的。
不需要真的用队列/栈模拟纸币，计数即可。

这是严格的在线决策：后面的钞票不能帮助前面的顾客找零。收到 10 元却没有 5 元，或收到 20 元且两种 15 元组合都不可用时，可以立即失败，不需要回溯之前的找零。

六、贪心选择为什么不会堵死未来

本题每一步选择是：收到20元时优先用10+5找15，只有没有10时才用三个5；20元钞票无法参与后续找零。

正确性不能只靠直觉，核心证明是：10元只能与5元组成15，而5元还能组成5或15；优先消耗用途更窄的10，保留更灵活的5。这说明任意最优方案都能调整为包含当前贪心选择的方案，且目标值不会变差。

排序或预处理，建立可比较的选择顺序
维护“当前选择给未来留下的有效边界”
若候选不劣于现有边界，则提交选择并更新状态

数字推演：[5,5,5,10,20] 最后用10+5成功；若此前把10视作无关则无法正确决策。

记忆钩子：贪心不是“选眼前最大”，而是选一个能被交换论证证明、对未来最宽松的代表。

七、退化边界、复杂度与反例检查

实现边界是：按顾客顺序在线处理，不能重排；收到10必须有5；收到20的两种方案都失败就立刻返回 false。

检查项	必须回答
排序键	为什么按这个维度和方向排序
局部选择	它保留了什么未来可能性
正确性	交换、领先或反证中的哪一种
失败边界	哪个题目条件一改就不能贪心
复杂度	排序成本与扫描成本是否都计入

测试时至少覆盖单元素、全部相等、严格递增/递减、恰好卡在边界、局部最优容易误导的反例。若无法写出交换论证或领先性质，应暂停使用贪心，转而尝试动态规划、搜索或数据结构。

反例可以验证找零优先级：若手里有一张 10 元和三张 5 元，给当前 20 元顾客使用三个 5 虽然也成功，却会让下一位 10 元顾客失去找零所需的 5；使用 10+5 则两位都能服务。

因此贪心保留的不是钞票总金额，而是未来找零组合的灵活性。5 元能参与两类找零，10 元只能参与 15 元找零，优先消耗用途更窄的资源。

八、常见误区与追问

误区：找20时三个5永远优先。 应优先10+5以保留两个更通用的5。
误区：20元可以给后面找零。 商品5元，后续找零只需5或15，20无法使用。
误区：可以先统计全部钞票再判断。 顾客顺序决定当时是否有零钱。
追问：交换论证是什么？ 把三个5替换为10+5不会影响当前成功且多留两个5。
追问：为什么不用回溯找零方案？ 币值和需求很小且贪心支配关系已证明。
追问：若商品价格或币值改变呢？ 该贪心未必成立，需要重新分析找零系统。

九、加强记忆

柠檬水找零 = 贪心模拟：只维护手上 5 元、10 元张数（20 元只进不出、不用记）。收 5 不找；收 10 找一张 5；收 20 找 15 时优先「10+5」，不够再拆「三张 5」——因为 5 元是万能零钱要尽量留（找 10、找 20 都靠它）。任何一步凑不出该找的零钱就返回 false。正确性靠交换论证：优先用 10 只会让后续更好找。O(n) 时间 O(1) 空间。

简化版

详细版