题目描述

解题思路

但仔细一琢磨就会发现，可供我们做判断的空间非常少！
只需要维护三种金额的数量，5，10和20。
有如下三种情况：

• 情况一：账单是5，直接收下。
• 情况二：账单是10，消耗一个5，增加一个10
• 情况三：账单是20，优先消耗一个10和一个5，如果不够，再消耗三个5

此时大家就发现 情况一，情况二，都是固定策略，都不用我们来做分析了，而唯一不确定的其实在情况三。
而情况三逻辑也不复杂甚至感觉纯模拟就可以了，其实情况三这里是有贪心的。
账单是20的情况，为什么要优先消耗一个10和一个5呢？
因为美元10只能给账单20找零，而美元5可以给账单10和账单20找零，美元5更万能！
所以局部最优：遇到账单20，优先消耗美元10，完成本次找零。全局最优：完成全部账单的找零。
局部最优可以推出全局最优，并找不出反例，那么就试试贪心算法！

public boolean lemonadeChange(int[] bills) {
    int five = 0, ten = 0, twenty = 0;
    for (int bill : bills) {
        if (bill == 5) {
            five++;
        }
        if (bill == 10) {
            if (five <= 0) return false;
            five--;
            ten++;
        }
        if (bill == 20) {
            // 优先消耗10美元，因为5美元的找零用处更大，能多留着就多留着(这里体现了贪心的策略)
            // 局部最优：遇到账单20，优先消耗美元10，完成本次找零。全局最优：完成全部账单的找零。
            if (ten > 0 && five > 0) {
                ten--;
                five--;
                twenty++;
            }
            else if (ten == 0 && five >= 3) {
                five = five - 3;
            }
            else return false;
        }
    }
    return true;
}