在柠檬水摊上，每一杯柠檬水的售价为 5 美元。顾客排队购买你的产品，（按账单 bills 支付的顺序）一次购买一杯。
每位顾客只买一杯柠檬水，然后向你付 5 美元、10 美元或 20 美元。你必须给每个顾客正确找零，也就是说净交易是每位顾客向你支付 5 美元。
注意，一开始你手头没有任何零钱。
给你一个整数数组 bills ，其中 bills[i] 是第 i 位顾客付的账。如果你能给每位顾客正确找零，返回 true ，否则返回 false 。
示例 1：
输入： bills = [5,5,5,10,20] 输出： true 解释： 前 3 位顾客那里，我们按顺序收取 3 张 5 美元的钞票。 第 4 位顾客那里，我们收取一张 10 美元的钞票，并返还 5 美元。 第 5 位顾客那里，我们找还一张 10 美元的钞票和一张 5 美元的钞票。 由于所有客户都得到了正确的找零，所以我们输出 true。 复制代码
示例 2：
输入： bills = [5,5,10,10,20] 输出： false 解释： 前 2 位顾客那里，我们按顺序收取 2 张 5 美元的钞票。 对于接下来的 2 位顾客，我们收取一张 10 美元的钞票，然后返还 5 美元。 对于最后一位顾客，我们无法退回 15 美元，因为我们现在只有两张 10 美元的钞票。 由于不是每位顾客都得到了正确的找零，所以答案是 false。 复制代码
示例 3：
输入： bills = [5,5,10] 输出： true 复制代码
示例 4：
输入： bills = [10,10] 输出： false 复制代码
提示：
1 <= bills.length <= 105bills[i]不是5就是10或是20
本题可以想到的一个最朴素的解题方法就是创建一个数组，记录钱包中的钞票，然后根据顾客付款的钞票面值选择是否找零及找零多少，如果能完成所有交易，则返回 true,否则返回 false
整个过程如下图：
这样的方式解题是可以通过的，但是效率比较低
因为每次都要去钱包查找是否有要找零的零钱，以及该零钱的位置并拿出
对应数组的操作就是要判断数组中是否有指定的数值，并找到该数值下标删除该数值
不知道大家有没有注意过超市的收银机是如何放置钱币的，它是类似下图这个样子的
可以看到图中对每种面值的钞票进行了分类放置
这样当需要判断某面值钞票是否存在的时候，只需要查看对应区间是否为空
而要找零的话，也只需要直接拿出最上面的一张即可
当零钱比较多或者需要多次找零的时候，这样处理对于效率的提升非常明显
这里我们的题解也是基于这种操作进行的
代码如下：
var lemonadeChange = function(bills) { // 记录5美元面值钞票数量 let num5 = 0, // 10美元面值钞票数量 num10 = 0; // 遍历每次交易 for(let i = 0;i<bills.length;i++){ switch(bills[i]){ // 如果5美元，直接收了 case 5: num5++; break; // 如果10美元 case 10: // 判断是否有5美元找零 if(num5){ num5--; num10++; // 没有返回 false }else return false; break; // 如果20美元 case 20: // 首先尝试10+5找零 if(num5&&num10){ num5--; num10--; // 再尝试5*3找零 }else if(num5>=3){ num5 -= 3; // 无法找零，返回false }else return false; } } // 所有交易都可以完成，返回true return true; }; 复制代码
这里要注意的是，为了可以进行更多的交易，所以要尽量留下更多的零钱
当顾客支付 20 美元的时候，可以选择找零 10+5，也可以选择找零 5*3
但是优先选择找零 10+5，因为我们要尽量的留下更多的 5 美元进行后续的交易找零
至此我们就完成了 leetcode-860-柠檬水找零
如有任何问题或建议，欢迎留言讨论！
