860. 柠檬水找零
问题描述
在柠檬水摊上，每一杯柠檬水售价5 美元。
顾客排队购买，每位顾客只买一杯，支付的金额可能是5、10 或 20 美元。
你最初没有任何零钱。你需要给每位顾客正确找零，使得净交易是每位顾客向你支付 5 美元。
注意：一开始你没有任何零钱。
返回true如果你能给每位顾客正确找零，否则返回false。
示例：
输入:[5,5,5,10,20]输出:true解释:-前三位顾客支付5美元，无需找零-第四位顾客支付10美元，找零5美元-第五位顾客支付20美元，找零15美元（一张10美元+一张5美元）输入:[5,5,10,10,20]输出:false解释:-前两位顾客支付5美元-第三位顾客支付10美元，找零5美元-第四位顾客支付10美元，找零5美元-第五位顾客支付20美元，需要找零15美元，但只剩2张5美元（10美元），无法找零输入:[5,5,10]输出:true算法思路
贪心算法：
核心：
- 5美元：无需找零，直接收下
- 10美元：必须找零5美元
- 20美元：需要找零15美元，有两种方式：
- 一张10美元 + 一张5美元（优先选择）
- 三张5美元
贪心策略：
- 对于20美元的找零，优先使用10美元，保留更多的5美元
- 5美元的用途更广（可以找零10美元和20美元），而10美元只能用于找零20美元
状态：
- 只需要记录当前拥有的5美元和10美元的数量
- 20美元不需要记录，因为无法用于找零
代码实现
方法一：贪心
classSolution{/** * 判断是否能给所有顾客正确找零 * 使用贪心：优先使用10美元找零20美元 * * @param bills 顾客支付的账单数组，每个元素为5、10或20 * @return 如果能正确找零返回true，否则返回false */publicbooleanlemonadeChange(int[]bills){intfive=0;// 5美元的数量intten=0;// 10美元的数量for(intbill:bills){if(bill==5){// 收到5美元，无需找零five++;}elseif(bill==10){// 收到10美元，需要找零5美元if(five>0){five--;ten++;}else{// 没有5美元找零returnfalse;}}else{// bill == 20// 收到20美元，需要找零15美元// 优先使用10+5的组合（贪心策略）if(ten>0&&five>0){ten--;five--;}elseif(five>=3){// 使用5+5+5的组合five-=3;}else{// 无法找零returnfalse;}}}returntrue;}}算法分析
- 时间复杂度：O(n)
- n 是顾客数量（bills数组长度）
- 每位顾客只需要O(1)时间处理
- 空间复杂度：O(1)
- 只使用了两个整数变量记录零钱数量
算法过程
1：bills = [5,5,5,10,20]
- 顾客1（5美元）：
five=1, ten=0 - 顾客2（5美元）：
five=2, ten=0 - 顾客3（5美元）：
five=3, ten=0 - 顾客4（10美元）：有5美元，
five=2, ten=1 - 顾客5（20美元）：有10美元和5美元，使用10+5组合，
five=1, ten=0 - 结果：
true
2：bills = [5,5,10,10,20]
- 顾客1（5美元）：
five=1, ten=0 - 顾客2（5美元）：
five=2, ten=0 - 顾客3（10美元）：
five=1, ten=1 - 顾客4（10美元）：
five=0, ten=2 - 顾客5（20美元）：
- 尝试10+5：有10美元但没有5美元
- 尝试5+5+5：只有0张5美元 < 3
- 结果：
false
测试用例
publicclassMain{publicstaticvoidmain(String[]args){Solutionsolution=newSolution();// 测试用例1：标准成功案例int[]bills1={5,5,5,10,20};System.out.println("Test 1: "+solution.lemonadeChange(bills1));// true// 测试用例2：找零失败int[]bills2={5,5,10,10,20};System.out.println("Test 2: "+solution.lemonadeChange(bills2));// false// 测试用例3：简单成功int[]bills3={5,5,10};System.out.println("Test 3: "+solution.lemonadeChange(bills3));// true// 测试用例4：只有5美元int[]bills4={5,5,5,5,5};System.out.println("Test 4: "+solution.lemonadeChange(bills4));// true// 测试用例5：第一个顾客付10美元int[]bills5={10,10};System.out.println("Test 5: "+solution.lemonadeChange(bills5));// false// 测试用例6：第一个顾客付20美元int[]bills6={20};System.out.println("Test 6: "+solution.lemonadeChange(bills6));// false// 测试用例7：复杂成功案例int[]bills7={5,5,10,20,5,5,5,5,5,5};System.out.println("Test 7: "+solution.lemonadeChange(bills7));// true// 测试用例8：边界情况 - 空数组int[]bills8={};System.out.println("Test 8: "+solution.lemonadeChange(bills8));// true// 测试用例9：单个5美元int[]bills9={5};System.out.println("Test 9: "+solution.lemonadeChange(bills9));// true// 测试用例10：全部20美元int[]bills10={20,20,20};System.out.println("Test 10: "+solution.lemonadeChange(bills10));// false// 测试用例11：贪心策略int[]bills11={5,5,5,5,10,20};System.out.println("Test 11: "+solution.lemonadeChange(bills11));// true// 如果错误地使用5+5+5找零20美元，会导致后续无法找零10美元// 贪心策略会保留5美元// 测试用例12：大量5美元int[]bills12=newint[10000];Arrays.fill(bills12,5);System.out.println("Test 12: "+solution.lemonadeChange(bills12));// true}}关键点
贪心策略：
- 5美元比10美元更有价值
- 优先消耗10美元，保留5美元
状态：
- 只需要跟踪5美元和10美元的数量
- 20美元无法用于找零，无需跟踪
边界条件处理：
- 空数组：返回true（没有顾客需要服务）
- 第一个顾客付10或20美元：无法找零，返回false
常见问题
为什么不用考虑20美元的数量？
20美元无法用于找零（只有5、10、20三种面额，20美元太大了），所以收到20美元后直接留在手里，不影响后续找零。贪心策略是否是最优的？
5美元的灵活性更高，保留更多5美元永远不会比消耗5美元更差。
)
