🍋860.柠檬水找零

在柠檬水摊上，每一杯柠檬水的售价为 5 美元。

顾客排队购买你的产品，（按账单 bills 支付的顺序）一次购买一杯。

每位顾客只买一杯柠檬水，然后向你付 5 美元、10 美元或 20 美元。你必须给每个顾客正确找零，也就是说净交易是每位顾客向你支付 5 美元。

注意，一开始你手头没有任何零钱。

如果你能给每位顾客正确找零，返回 true ，否则返回 false 。

示例

示例 1：

• 输入：[5,5,5,10,20]
• 输出：true
• 解释：
  • 前 3 位顾客那里，我们按顺序收取 3 张 5 美元的钞票。
  • 第 4 位顾客那里，我们收取一张 10 美元的钞票，并返还 5 美元。
  • 第 5 位顾客那里，我们找还一张 10 美元的钞票和一张 5 美元的钞票。
  • 由于所有客户都得到了正确的找零，所以我们输出 true。

示例 2：

• 输入：[5,5,10]
• 输出：true

示例 3：

• 输入：[10,10]
• 输出：false

示例 4：

• 输入：[5,5,10,10,20]
• 输出：false
• 解释：
  • 前 2 位顾客那里，我们按顺序收取 2 张 5 美元的钞票。
  • 对于接下来的 2 位顾客，我们收取一张 10 美元的钞票，然后返还 5 美元。
  • 对于最后一位顾客，我们无法退回 15 美元，因为我们现在只有两张 10 美元的钞票。
  • 由于不是每位顾客都得到了正确的找零，所以答案是 false。

提示：

• 0 <= bills.length <= 10000
• bills[i] 不是 5 就是 10 或是 20

思路

基本思想

第一想法就是顾客之间进行组合，10美元的顾客需要先有一个5美元的顾客消费，20美元的顾客需要有一个10美元，一个5美元的顾客消费或者三个5美元的顾客消费

这样才能保证可以找零

但是看到示例4发现还需要知道每种金额的数量，虽然余额为20，但是因为是两张10美金，所以无法给20美金的顾客正确找零，也就是找不开

所以可以维护两个标志，分别是5美金和10美金的个数，遇到不同的顾客对应处理不同的标志

执行流程

遍历容器，设置两个标志记录5美金和10美金的数量

1. 遇到5美金的顾客，直接将记录5的标志++

2. 遇到10美金的顾客，判断是否还有5美金，没有返回false

3. 遇到20美金的顾客，先判断是否还有10+5的组合，再判断是否还有3*5的组合，没有返回false

4. 遍历结束都没有出现无法找零的情况，返回true

只有10美金和20美金才找零，而10美金只能给20美金找零，5美金可以给10和20美金找零，更为通用，所以尽量把通用的5美元放在最后用

和小商贩卖菜是一样的道理，都希望手上零钱更多

代码

根据以上分析，得出以下代码：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41

class Solution {
public:
    bool lemonadeChange(vector<int>& bills) {
        int five=0;
        int ten=0;
        for(auto elem : bills){
            //5美金，不用找零
            if(elem==5){
                ++five;
            }
            //10美金
            if(elem==10){
                //够找零
                if(five>0){
                    five--;
                    ten++;
                }
                else{
                    return false;
                }
            }
            //20美金
            if(elem==20){
                //优先使用10+5的找零组合
                if(ten>0&&five>0){
                    ten--;
                    five--;
                }
                //在使用3*5的找零组合
                else if(five>=3){
                    five-=3;
                }
                else{
                   return false; 
                }
            }
        }
        //遍历结束都没有出现无法找零的情况
        return true;
    }
};

总结

只需要简单模拟消费和找零的情况即可，遇到20美元时，优先使用10+5的找零组合，尽可能留下通用的5美元，防止后面出现余额足够但是找不开（示例4）的情况