860. 柠檬水找零
内容提要
这篇文章讲述了一个关于柠檬水找零的问题。顾客在柠檬水摊位上购买柠檬水，每杯柠檬水的价格为5美元。顾客按照账单的顺序依次购买，每个顾客只购买一杯柠檬水，并用5美元、10美元或20美元的钞票支付。文章提供了一个整数数组bills，其中bills[i]表示第i个顾客支付的账单。如果能够给每个顾客正确找零，则返回true，否则返回false。解决方案是模拟给顾客找零的过程，并跟踪手中的5美元和10美元的数量。如果成功处理所有顾客而不用找零，则返回true。
延伸解读
贪心策略的合理性
在找零过程中，优先使用10美元和5美元的组合为20美元找零，而不是用三张5美元，这体现了贪心思想。因为5美元更灵活，既能用于10美元的找零，也能用于20美元的找零，而10美元只能用于20美元的找零。保留更多5美元可以应对后续可能出现的10美元支付，从而降低无法找零的风险。
边界情况与失败条件
算法需要处理顾客支付大额钞票时手中零钱不足的情况。例如，第一个顾客就支付10美元或20美元，由于初始没有任何零钱，无法找零，直接返回false。同样，如果连续收到多个10美元而5美元耗尽，后续的10美元支付也会失败。这些边界情况是判断能否成功的关键。
时间与空间复杂度
该解法只需遍历一次账单数组，对每个顾客进行常数次操作，因此时间复杂度为O(n)，其中n是顾客数量。空间上仅需两个变量记录5美元和10美元的数量，复杂度为O(1)。这种高效性使其能轻松处理最多100,000个顾客的输入规模。
Q&A
柠檬水的价格是多少？
每杯柠檬水的价格为5美元。
顾客可以用什么钞票支付柠檬水？
顾客可以使用5美元、10美元或20美元的钞票支付。
如何判断能否给每位顾客正确找零？
通过模拟找零过程，跟踪手中5美元和10美元的数量来判断。
支付20美元时应该如何找零？
优先用1个10美元和1个5美元找零，如果不够则用3个5美元找零。
如果没有足够的钞票找零会怎样？
如果没有足够的钞票找零，则返回false。
这个问题的时间复杂度是多少？
解决方案的时间复杂度为O(n)。
