DEV Community
·
860. 柠檬水找零
原文英文，约700词，阅读约需3分钟。
📝
内容提要
这篇文章讲述了一个关于柠檬水找零的问题。顾客在柠檬水摊位上购买柠檬水，每杯柠檬水的价格为5美元。顾客按照账单的顺序依次购买，每个顾客只购买一杯柠檬水，并用5美元、10美元或20美元的钞票支付。文章提供了一个整数数组bills，其中bills[i]表示第i个顾客支付的账单。如果能够给每个顾客正确找零，则返回true，否则返回false。解决方案是模拟给顾客找零的过程，并跟踪手中的5美元和10美元的数量。如果成功处理所有顾客而不用找零，则返回true。
🎯
关键要点
-
柠檬水每杯售价为5美元，顾客依次购买并支付。
-
顾客可以使用5美元、10美元或20美元的钞票支付。
-
需要正确找零给每位顾客，若能做到则返回true，否则返回false。
-
解决方案是模拟找零过程，跟踪手中5美元和10美元的数量。
-
支付5美元时，增加5美元的数量；支付10美元时，减少1个5美元；支付20美元时，优先用1个10美元和1个5美元找零。
-
如果没有足够的钞票找零，则返回false。
-
函数应处理无法找零的边界情况，并高效处理大输入规模，时间复杂度为O(n)。
❓
延伸问答
柠檬水的价格是多少？
每杯柠檬水的价格为5美元。
顾客可以用什么钞票支付柠檬水？
顾客可以使用5美元、10美元或20美元的钞票支付。
如何判断能否给每位顾客正确找零？
通过模拟找零过程，跟踪手中5美元和10美元的数量来判断。
支付20美元时应该如何找零？
优先用1个10美元和1个5美元找零，如果不够则用3个5美元找零。
如果没有足够的钞票找零会怎样？
如果没有足够的钞票找零，则返回false。
这个问题的时间复杂度是多少？
解决方案的时间复杂度为O(n)。
