数字与贪心

• 860. Lemonade Change
  • 思路
  • C++解法

860. Lemonade Change

At a lemonade stand, each lemonade costs $5. Customers are standing in a queue to buy from you and order one at a time (in the order specified by bills). Each customer will only buy one lemonade and pay with either a $5, $10, or $20 bill. You must provide the correct change to each customer so that the net transaction is that the customer pays $5.

Note that you do not have any change in hand at first.

Given an integer array bills where bills[i] is the bill the ith customer pays, return true if you can provide every customer with the correct change, or false otherwise.

Example 1:

Input: bills = [5,5,5,10,20]
Output: true
Explanation: From the first 3 customers, we collect three $5billsinorder.Fromthefourthcustomer,wecollecta$10 bill and give back a $5.Fromthefifthcustomer,wegivea$10 bill and a $5bill.Sinceallcustomersgotcorrectchange,weoutputtrue.\ast \ast Example2:\ast \ast \ast \ast Input:\ast \ast bills=[5,5,10,10,20]\ast \ast Output:\ast \ast false\ast \ast Explanation:\ast \ast Fromthefirsttwocustomersinorder,wecollecttwo$5 bills. For the next two customers in order, we collect a $10billandgivebacka$5 bill. For the last customer, we can not give the change of $15backbecauseweonlyhavetwo$10 bills. Since not every customer received the correct change, the answer is false.

Constraints:

• 1 <= bills.length <= 10^5
• bills[i] is either 5, 10, or 20.

思路

这道题目刚一看，可能会有点懵，这要怎么找零才能保证完成全部账单的找零呢？

但仔细一琢磨就会发现，可供我们做判断的空间非常少！

只需要维护三种金额的数量，5，10和20。

有如下三种情况：

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

此时大家就发现 情况一，情况二，都是固定策略，都不用我们来做分析了，而唯一不确定的其实在情况三。

而情况三逻辑也不复杂甚至感觉纯模拟就可以了，其实情况三这里是有贪心的。

账单是20的情况，为什么要优先消耗一个10和一个5呢？

因为美元10只能给账单20找零，而美元5可以给账单10和账单20找零，美元5更万能！

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

局部最优可以推出全局最优，并找不出反例，那么就试试贪心算法！

C++解法

C++代码如下：

class Solution {  
public:  
    bool lemonadeChange(vector<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;  
                ten++;  
                five--;  
            }  
            // 情况三  
            if (bill == 20) {  
                // 优先消耗10美元，因为5美元的找零用处更大，能多留着就多留着  
                if (five > 0 && ten > 0) {  
                    five--;  
                    ten--;  
                    twenty++; // 其实这行代码可以删了，因为记录20已经没有意义了，不会用20来找零  
                } else if (five >= 3) {  
                    five -= 3;  
                    twenty++; // 同理，这行代码也可以删了  
                } else return false;  
            }  
        }  
        return true;  
    }  
};

• 时间复杂度: O(n)
• 空间复杂度: O(1)