【贪心算法】：LeetCode860.柠檬水找零

朋友们、伙计们，我们又见面了，本专栏是关于各种算法的解析，如果看完之后对你有一定的启发，那么请留下你的三连，祝大家心想事成！

C 语言专栏：C语言：从入门到精通

数据结构专栏：数据结构

个人主页：stackY、

C + + 专栏：C++

Linux 专栏：Linux

1. 题目解析

2. 算法原理讲解

3. 代码实现

4. 贪心策略证明

1. 题目解析

LeetCode860.柠檬水找零：https://leetcode.cn/problems/lemonade-change/description/https://leetcode.cn/problems/lemonade-change/description/

860. 柠檬水找零

在柠檬水摊上，每一杯柠檬水的售价为 5 美元。顾客排队购买你的产品，（按账单 bills 支付的顺序）一次购买一杯。

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

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

给你一个整数数组 bills ，其中 bills[i] 是第 i 位顾客付的账。如果你能给每位顾客正确找零，返回 true ，否则返回 false 。

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

1 <= bills.length <= 105
bills[i] 不是 5 就是 10 或是 20

根据题意：首先找零是按照顺序来进行的，不能“插队”，并且刚开始我们身无分文。

假设第一个顾客给5块，那么直接收下即可；

如果第一个顾客给的不是5块，那表示需要给顾客找零，但是此时我们没有钱，所以直接返回false即可。

2. 算法原理讲解

首先：我们根据顾客支付的钱可以分为三种情况：

1. 顾客支付5元 -> 直接收下即可；

2. 顾客支付10元 -> 直接收下，并且判断身上是否有5元，如果有找零给顾客，如果没有直接返回false；

3. 顾客支付20元 -> 直接收下，此时给顾客找零就存在两种方法：

① 找给顾客一张10元和一张5元；

② 找给顾客三张5元；

那么该如何选择上述两种情况呢？

就需要用到贪心算法，那么到底该怎么贪才是最优呢？

上面的两种方法其本质上就是一张10元与两张5元的区别，那么根据贪心策略该怎么贪呢？

仔细观察不难发现，5元的用处是很大的，不仅可以给10元找零，还可以给20元找零，那么既然5元用处这么大，就表示5元比较珍贵，所以越珍贵的东西我们越舍不得用，所以尽量选择找零5元比较少的那一个方法，所以我们的贪心策略是：尽可能少的使用5元钱给顾客找零。

3. 代码实现

怎么记录我们手上的钱呢？

可以使用两个变量来统计此时我们手中所具有的5元钱的张数（cnt_five）和10元钱cnt_ten），然后遍历bills，遇到5元将cnt_five++，遇到10元钱先看自己手里有没有钱，遇到20元首先考虑的就是10+5的策略，再考虑5+5+5的策略。

class Solution 
{
public:
    bool lemonadeChange(vector<int>& bills) 
    {
        //统计5元钱和10元钱的张数
        int cnt_ten = 0, cnt_five = 0; 
        //遍历
        for(auto& e : bills)
        {
            if(e == 5) cnt_five++;   //遇到5元就收下
            else if(e == 10)         //遇到10元
            {
                cnt_ten++;
                if(cnt_five) cnt_five--; //先判断是否可以找零
                else return false;
            }
            else                     //遇到20元
            {
                if(cnt_five && cnt_ten) //先考虑10+5的策略
                {
                    cnt_five--;
                    cnt_ten--;
                }
                else if(cnt_five >= 3) cnt_five -= 3; //再考虑5+5+5的策略
                else return false;
            }
        }
        //走到这里就说明找零成功
        return true;
    }
};

4. 贪心策略证明

那么如果证明我们选择的这种贪心策略是否正确呢？

需要用到：交换论证法

例如：

假设贪心解为 [a, b, c, d, e, f]

假设最优解为 [e, b, c, d, a, f]

交换论证就是在不破坏最优解的“最优性质”的前提下可以通过一定的调整将最优解转化为贪心解即可

将最优解里面的e和a交换，这样既没有破坏最优解性质，同样也可以将最优解转化为贪心解，则表示该贪心策略正确。

在本题中使用交换论证法：遇到顾客给20元，贪心解是用10元和5元进行找零，最优解是用三张5元进行找零，区别就在于两张5元和一张10元。

顾客 ... 5 10 20 10 ...

贪心解 ... 0 5 10+5 5 ...

最优解 ... 0 5 5+5+5 5 ...

那么在整个找零过程中，最优解的10元存在花与不花两种情况：

① 如果在前面或者后面的找零过程中，将10元钱花了，那么在后面花的10元钱可以将这里的5+5给替换掉，此时也就变成了贪心解；

② 如果在前面或者后面的找零过程中，没有将10钱花掉，那么就可以用没花掉的10元钱替换掉这里的5+5，此时也变成了贪心解。

所以通过交换论证法证明了最优解可以在不改变最优条件的性质下变成贪心解，所以证明我们的贪心策略（选择花费5元较少的一种方法）是正确的。