1. 问题背景与需求分析今天想和大家分享一道LeetCode上非常经典的贪心算法题目——860.柠檬水找零Lemonade Change。这道题在面试中出现的频率相当高特别是在考察基础算法思维时。我自己在刷这道题时最初提交的解法耗时是100ms后来经过优化达到了更优的性能。下面就来详细拆解这道题的解题思路和优化过程。题目描述很简单你经营一个柠檬水摊每杯柠檬水售价5美元。顾客排队购买每次只买一杯柠檬水并按顺序付钱5美元、10美元或20美元。你需要给每位顾客正确找零。开始时你手头没有任何零钱。如果能给所有顾客正确找零返回true否则返回false。2. 核心算法思路解析2.1 贪心算法选择这道题最直观的解法就是使用贪心算法。贪心算法在这类找零问题中特别适用因为我们需要在每一步做出局部最优的选择而这些局部最优解最终会导向全局最优解。具体到这道题我们需要维护两种零钱的数量5美元和10美元20美元不需要找零所以不用记录。当收到不同面额时采取不同的找零策略收到5美元不需要找零5美元数量1收到10美元必须找一张5美元5美元数量-110美元数量1收到20美元优先使用105的组合找零因为10美元只能用于找零20美元的情况如果没有10美元再用三张5美元2.2 为什么贪心算法有效这里有个关键点需要理解为什么在收到20美元时要优先使用105的组合而不是三张5美元这是因为5美元更加通用既可以用于找零10美元也可以用于找零20美元。如果我们在可以找105时却用了三张5美元可能会导致后续遇到需要找零10美元时没有足够的5美元。举个例子 假设当前零钱5美元×310美元×0 顾客支付顺序10美元20美元 如果第一次收到10美元时用三张5美元找零虽然题目要求是找一张5美元这里只是举例说明思路那么遇到20美元时就无法找零了。3. 代码实现与优化3.1 基础实现先来看最基础的实现方式这也是我最初提交的耗时100ms的版本def lemonadeChange(bills): five ten 0 for bill in bills: if bill 5: five 1 elif bill 10: if not five: return False five - 1 ten 1 else: # 20 if ten and five: ten - 1 five - 1 elif five 3: five - 3 else: return False return True这个实现非常直观维护两个计数器five和ten分别记录5美元和10美元的数量。对于每个顾客的支付按照前述策略进行处理。3.2 性能优化虽然上述解法已经能够正确解决问题但在LeetCode上提交时耗时100ms说明还有优化空间。经过分析我发现可以做一些微优化将if not five改为if five 0因为直接比较数字比布尔转换稍快在20美元的处理中将条件判断顺序调整先检查更可能的情况使用局部变量而不是多次访问实例变量优化后的代码如下def lemonadeChange(bills): five ten 0 for bill in bills: if bill 5: five 1 elif bill 10: if five 0: return False five - 1 ten 1 else: # 20 if five 0: return False if ten 0: ten - 1 five - 1 else: if five 3: return False five - 3 return True这个优化版本在LeetCode上的运行时间可以提升到80ms左右。虽然看似微小的改进但在算法竞赛或面试中这种优化意识是很重要的。4. 边界条件与测试用例4.1 关键测试用例为了确保代码的正确性我们需要考虑各种边界情况。以下是一些重要的测试用例全部支付5美元[5,5,5,5] → True需要找零但零钱不足[5,10,20] → False复杂但可行的找零[5,5,10,10,20] → True零钱刚好用完[5,10,5,20] → True大额支付连续[5,5,10,20,20] → False4.2 特殊情况的处理在实际编码中有几个特殊情况需要注意第一个顾客支付的不是5美元直接返回False因为没有零钱找收到20美元时有多种找零方式必须优先使用105的组合零钱刚好用完的情况需要精确计算不能有丝毫偏差5. 算法复杂度分析让我们分析一下这个算法的时间和空间复杂度时间复杂度O(n)其中n是bills数组的长度。我们只需要遍历一次数组每个顾客的处理都是O(1)的操作。空间复杂度O(1)我们只使用了两个额外的变量来存储5美元和10美元的数量与输入规模无关。这种线性时间复杂度和常数空间复杂度使得该算法非常高效能够处理大规模输入。6. 同类问题扩展掌握了这道题后可以尝试解决一些类似的找零或贪心算法问题硬币找零问题Coin Change给定不同面额的硬币和一个总金额计算可以凑成总金额的最少硬币数。加油站问题Gas Station环形路线上有N个加油站每个加油站有可加的油量和到下一站的距离判断从哪个加油站出发可以绕行一周。分发饼干Assign Cookies每个孩子有一个满足度每个饼干有一个大小求最多可以满足多少个孩子。这些问题都使用了贪心算法的思想通过局部最优选择来达到全局最优解。7. 实际应用场景虽然题目设定是柠檬水摊但这种找零算法在实际中有广泛的应用自动售货机的找零系统收银软件的找零算法金融系统中的零钱兑换游戏中的虚拟货币交易系统理解这个算法有助于我们在实际开发中设计更高效的货币处理系统。8. 常见错误与调试技巧在解决这个问题时新手常会犯以下几种错误没有优先使用105的组合找零20美元导致后续无法找零10美元忽略了第一个顾客必须支付5美元的情况在找零时没有先检查是否有足够的零钱就直接扣除调试技巧打印出每次交易后的5美元和10美元数量方便追踪状态变化使用小规模的测试用例手动模拟算法执行过程特别注意边界条件如零钱刚好用完的情况9. 不同语言的实现差异虽然算法逻辑相同但在不同编程语言中实现时会有一些差异9.1 Java实现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 { if (five 0 ten 0) { five--; ten--; } else if (five 3) { five - 3; } else { return false; } } } return true; }9.2 C实现bool lemonadeChange(vectorint 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 { if (five 0 ten 0) { five--; ten--; } else if (five 3) { five - 3; } else { return false; } } } return true; }9.3 JavaScript实现function lemonadeChange(bills) { let five 0, ten 0; for (const bill of bills) { if (bill 5) { five; } else if (bill 10) { if (five 0) return false; five--; ten; } else { if (five 0 ten 0) { five--; ten--; } else if (five 3) { five - 3; } else { return false; } } } return true; }不同语言在语法上有差异但核心逻辑完全一致。选择哪种语言实现主要取决于你的使用场景和偏好。10. 进一步优化思路虽然我们已经达到了O(n)的时间复杂度但仍有一些可能的优化方向提前终止如果在某个点发现5美元的数量为负可以立即返回False使用位运算对于非常大的输入可以考虑用位运算来记录状态虽然对于这个问题可能有点过度优化并行处理如果输入规模极大可以考虑并行处理不同的区段需要额外处理区段间的状态传递不过对于LeetCode上的这道题最初的优化版本已经足够好了这些进一步的优化更多是理论上的探讨。11. 面试中的应用这道题在面试中经常出现因为它很好地考察了基础编码能力贪心算法的理解边界条件的处理问题分析能力在面试中解答这道题时建议先明确问题确认理解正确提出暴力解法如果有的话然后优化解释为什么贪心算法适用讨论时间复杂度和空间复杂度提出测试用例特别是边界情况如果时间允许讨论可能的优化和变种12. 个人心得与总结在刷这道题的过程中我最大的收获是对贪心算法有了更深入的理解。最初我可能会尝试用动态规划来解决但后来意识到贪心算法更加高效。关键在于识别问题是否具有贪心选择性质——即局部最优解能导致全局最优解。另一个重要的体会是找零策略的选择。优先使用105而不是三张5美元这个看似简单的决策背后其实体现了对问题更深入的理解。这也提醒我在解决其他问题时要仔细考虑不同策略的长期影响。
