力扣860-柠檬水找零（java详细题解）

本文主要是介绍力扣860-柠檬水找零（java详细题解），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目链接：860. 柠檬水找零 - 力扣（LeetCode）

前情提要：

因为本人最近都来刷贪心类的题目所以该题就默认用贪心方法来做。

贪心方法：局部最优推出全局最优。

如果一个题你觉得可以用局部最优推出全局最优，并且没有反例来反驳的话就可以用贪心来试试。

题目思路：

该题其实蛮好入手，因为他只有三种逻辑的处理方式。

1.当顾客给你5块，你不用找零，手下这5块。

2.当顾客给你10块，你只能用5来找零，没有的话返回false；

3.当顾客给你20块，此时你有俩种方式找零

给一个10块和一个5块
给三个5块

那么我们该如何选择呢？

其实这里我们就用到了贪心。

我们应该优先选择第一种方式，因为5块更有用，如果你在20块将所有的5块用完了，后面还有一位顾客给你10块呢，那就找不了零了。

但是如果选第一种方式，这样的情况就会避免。

所以我们贪在选第一种方式。

局部最优：遇到账单20，优先消耗美元10，完成本次找零。

全局最优：完成全部账单的找

最终代码:

class Solution {public boolean lemonadeChange(int[] bills) {//定义每一种零钱的数量int five = 0,ten = 0;for(int i = 0;i < bills.length;i ++){//当遇到5美元时if(bills[i] == 5){five ++;//遇到10美元时}else if(bills[i] == 10){if(five < 0){return false;}ten ++;five --;//遇到20美元时}else{//优先采用第一种策略if(ten > 0 && five > 0){ten --;five--;}else if(five - 3 >= 0){five -= 3;//俩种策略都不行，返回false}else{return false;}}}return true;}
}