Leetcode 860 柠檬水找零

题意理解：

? ? ? ? 已知每杯柠檬水5元，最开始你没有钱，客户可能付给你的面额有5，10，20

? ? ? ? bills=[5,5,5,10,20]表示每单客户付的钱

? ? ? ? 目标：成功完成每单，且合理找零。

? ? ? ? ? ? ? ? ? ?若无零钱找零则失败。

解题思路：

? ? ? ? 使用贪心算法的思路来解题，首先明确什么是全局最优解，什么是局部最优解。

? ? ? ? 全局最优解，总是能找零客户的账单

? ? ? ? 局部最优解：为了能找零客户账单，应尽量保存面额小的纸币

? ? ? ? 如20元账单找零：? ?10+5? ? ?5+5+5

? ? ? ? 10元的账单找零：? ? 5

? ? ? ? 即：小面额纸币总是拥有较大的自由度，能为提供更多的找零方式，所以我们优先消耗10元找零，保存尽可能多的5元。

1.贪心解题

我们用five、ten、twenty记录各个面值纸币的数量

public boolean lemonadeChange(int[] bills) {
        int five=0,ten=0,twenty=0;
        //遍历所有账单
        for(int i=0;i<bills.length;i++){
            //付款5元：不找零
            if(bills[i]==5) five++;
            //付款10元：需找零
            if(bills[i]==10){
                if(five>0){//10元可找零
                    five--;
                    ten++;
                }else {
                    return false;//10元无法找零
                }
            }
            //付款20元：需找零
            if(bills[i]==20) {
                if (ten > 0 && five > 0) {//20元可找零:10+5
                    five--;
                    ten--;
                    twenty++;
                } else if (ten == 0 && five >= 3) {//20元可找零:5+5+5
                    five -= 3;
                    twenty++;
                } else {//20元不可找零
                    return false;
                }

            }
        }
        return true;
    }

2.分析?

时间复杂度：O(n)

空间复杂度：O(1)

n为输入数组长度