### Lemonade Change 问题的定义与解决方案 Lemonade change 是一个经典的贪心算法问题，描述如下：柠檬水摊主出售每杯售价为 $5 的柠檬水。顾客依次购买并支付金额分别为 $5、$10 或 $20。摊主最初没有任何零钱可用。每次交易时，摊主要确保能够向每位支付超过 $5 的顾客提供足够的找零。如果无法完成某次交易，则返回 `False` 表示失败；否则返回 `True` 表示成功完成所有交易[^4]。 此问题的核心在于维护手头拥有的不同面额钞票数量，并按照最优策略分配找零以最大化后续交易的可能性。 --- #### 解决方案分析 一种有效的解决方式是基于贪心算法的思想来模拟整个销售流程： - 定义两个计数器分别记录当前持有的 `$5` 和 `$10` 钞票的数量。 - 遍历每一位顾客所付的钱款数额： - 如果收到的是 `$5`，无需找零，直接增加对应计数； - 收到 `$10` 时，尝试找出一张 `$5` 给予找零，若无足够 `$5` 则立即返回 `False`； - 收到 `$20` 时，优先尝试用一张 `$10` 加上一张 `$5` 进行组合找零（因为这样保留更多单独的小额钞票有助于未来更灵活应对需求），如果没有合适组合再考虑仅使用三张 `$5` 实现找零。同样地，一旦发现不足以满足条件便立刻终止程序运行并给出否定答复。 这种方法之所以可行是因为它始终遵循局部最优原则——即每当面临多种可能的选择时总是挑选那个看起来当下最为有利的那个选项，从而期望达到全局范围内的最好效果。 以下是具体的 Python 函数实现版本： ```python def lemonadeChange(bills): five, ten = 0, 0 for bill in bills: if bill == 5: five += 1 elif bill == 10: if five == 0: return False five -= 1 ten += 1 else: # bill == 20 if ten > 0 and five > 0: ten -= 1 five -= 1 elif five >= 3: five -= 3 else: return False return True ``` 上述代码逻辑清晰简洁，完全依照前述思路逐一处理输入数组中的每一个元素直到结束为止。 --- #### 复杂度评估 时间复杂度 O(n)，其中 n 是列表 bills 的长度。这是因为我们需要遍历一遍给定的账单序列来进行相应的操作判定。 空间复杂度 O(1)，因为我们只用了常量级额外存储空间(five 和 ten 计数器) 来辅助运算过程[^5]。 --- #### 示例演示 让我们看几个简单的测试案例以便更好地理解这个函数的工作机制: ```python print(lemonadeChange([5, 5, 5, 10, 20])) # 输出应为 True print(lemonadeChange([5, 5, 10, 10, 20])) # 输出应为 False ``` 第一个例子展示了理想状况下顺利完成了全部交易的情形；而在第二个例子当中由于缺乏必要的小额钞票致使最后一位持有二十元纸币的大客户得不到应有的服务因而整体被判为失败。 ---