(每日一题) 力扣 860 柠檬水找零

LeetCode 860. 柠檬水找零题解

问题描述

在柠檬水摊上，每杯柠檬水售价 5 美元。顾客按顺序支付 5、10 或 20 美元，你需要正确找零（开始时无零钱）。若所有顾客都能成功找零，返回 true，否则返回 false。

解题思路

贪心算法是本题的最优解，核心在于优先使用高面额零钱，保留灵活的小面额零钱应对后续找零需求。

关键步骤：

1. 初始化零钱数量：用 five 和 ten 分别记录 5 美元和 10 美元的数量。
2. 遍历账单：
   • 收到 5 美元：直接收下，无需找零。
   • 收到 10 美元：需找 5 美元，若无则失败。
   • 收到 20 美元：优先找 10+5 美元的组合，若无则找 3 个 5 美元。若均无法满足，失败。

代码实现（C++）

class Solution {
public:
    bool lemonadeChange(vector<int>& bills) {
        int five = 0, ten = 0;
        for (auto& e : bills) {
            if (e == 5) {
                ++five;
            } else if (e == 10) {
                if (five == 0) return false;
                --five;
                ++ten;
            } else {
                // 优先用 10+5 找零
                if (five > 0 && ten > 0) {
                    --five;
                    --ten;
                } else if (five >= 3) {
                    five -= 3;
                } else {
                    return false;
                }
            }
        }
        return true;
    }
};

算法分析

• 时间复杂度：O(n)，仅需遍历一次账单数组。
• 空间复杂度：O(1)，仅用两个变量记录零钱数量。

示例图解

以输入 bills = [5,5,5,10,20] 为例：

最终 five=1, ten=0，成功找零，返回 true。

贪心策略的正确性证明

• 为何优先用 10+5 找零 20 美元？
  5 美元可应对更多场景（如找零 10 美元需 1 张，找零 20 美元需 3 张），而 10 美元只能用于找零 20 美元。优先消耗 10 美元可保留 5 美元的灵活性。

边界条件与测试用例

1. 首顾客支付非 5 美元：直接失败（如 bills = [10]）。
2. 中途零钱不足：如 [5,5,10,10,20]，最后一位顾客需找 15 美元但只剩 10 美元，失败。
3. 大额支付需组合找零：如 [5,10,20]，需正确处理 20 美元的两种找零方式。

总结

本题通过贪心策略，在保证每一步局部最优（保留最多 5 美元）的同时实现全局最优解。关键点在于零钱面额的使用优先级和边界条件的处理。