在柠檬水摊上，每一杯柠檬水的售价为 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 <= 105bills[i]不是5就是10或是20
解题思路：贪心算法
这道题其实算是很简单的贪心算法题了，即使我们不适用贪心策略也能顺势写出贪心策略的解法！
根据题目要求，无非就是根据顾客支付的钱的大小，分情况进行讨论，不过我们需要用两个变量 five 和 ten 分别表示 5 块钱和 10 块钱的零花钱数量，这里是不需要记录 20 块钱的零花钱数量的，因为顾客最多也就是支付 20 块钱，而我们要给他找零最多也就是 15 块钱，是不可能给它找零 20 块钱的，所以不需要关心 20 块钱的零花钱数量！
下面分情况讨论：
- 如果顾客支付
5块钱：- 这种情况最简单，此时我们就拿到了一张
5块钱的零钱，则让five++即可。
- 这种情况最简单，此时我们就拿到了一张
- 如果顾客支付
10块钱：- 这个时候我们需要给顾客找零
5块钱，所以需要先判断一下five是否不为零，如果为零说明交易失败，则直接返回false；如果不为零，则给顾客找零一张5块钱，也就是让five--，然后让ten++就行！
- 这个时候我们需要给顾客找零
- 如果顾客支付
20块钱：- 因为要给顾客找零
15块钱，所以有以下两种情况：- 找零一张
10块钱和一张5块钱。 - 找零三张
5块钱。
- 找零一张
- 那么此时我们应该优先选择哪种策略呢❓❓❓
- 其实最好优先选择第一种策略，因为对我们来说，
5块钱零钱的功能要比10块钱多，因为5块钱既能给10块钱找零，又能给20块钱找零，那么我们就要尽量保留5块零钱，留到后面才有更多的选择，也就是有10块零钱的话就优先花掉！
- 因为要给顾客找零
最后代码并不难实现，就是分情况讨论，如下所示：
class Solution {
public:
bool lemonadeChange(vector<int>& bills) {
int five = 0, ten = 0; // 表示零钱的数量，这里不需要用到20块钱的零钱
for(int i = 0; i < bills.size(); ++i)
{
if(bills[i] == 5)
{
five++;
}
else if(bills[i] == 10)
{
if(five == 0)
return false;
five--;
ten++;
}
else
{
// 贪心策略：尽量保留功能更多的5块钱，也就是尽量花10块钱
if(ten != 0 && five != 0)
{
ten--;
five--;
}
else if(ten == 0 && five >= 3)
{
five -= 3;
}
else
return false;
}
}
return true;
}
};交换论证法
交换论证法是证明贪心策略常见的一种方法，后面我们会经常使用到！其思路也很简单：在不破坏最优解的 “最优性质” 的前提下，能够将最优解调整成我们的贪心解的话，则该贪心解就是最优解！
就以这道题为例子，做以下假设：
- 贪心解：…… +
10+5+ …… - 最优解：…… +
5+5+5+ ……
当给 20 块钱找零钱的时候，此时出现了贪心解中的 10+5 以及最优解对应的 5+5+5，对于最优解来说，有两种情况：
- 如果最优解后面省略的部分中没有使用到
10，也就是说还有10块钱零钱，那么此时就可以将最优解的5+5+5替换成10+5，得到与贪心解这部分相同的结果。 - 如果最优解后面省略的部分中使用到了**
10**，那么我们可以让后面的10和前面的5+5进行交换，因为这都能给20块钱找零钱，所以对于最优解来说交换两者是没有影响的，此时前面又变成了10+5，同样得到与贪心解这部分相同的结果。
可以发现，通过交换论证法可以在不破坏最优解性质前提下转化为贪心解，则说明该贪心解就是最优解！