信用湘潭网站网站开发项目教程笔记

力扣原题链接，点击跳转。

假设你的手里没有钱。你要卖柠檬水，每杯5块钱。每个顾客有可能会给你5块钱、10块钱或20块钱，你要拿手中的钱找零。如何判断你能否成功找零呢？

如果一上来就有顾客花10块钱或20块钱，你手中没有钱，自然无法找零。我们考虑一下能找零的情况。如果有顾客花10块钱，你就要找5块钱，如果你手里没有5块钱，则找零失败。如果有顾客花20块钱，你可以找一张10块钱和一张5块钱，或者三张5块钱。如果是你，你会选择一张10块钱和一张5块钱，还是三张5块钱呢？显然，10块钱的作用并不大，只有顾客花20块钱时，才有可能用作找零；但是5块钱的作用就非常大了，不管顾客花10块钱还是20块钱，都有可能用作找零。所以，我们应尽可能把作用不大的10块钱花出去，把作用较大的5块钱留在手里，这就是贪心策略。换句话说，我们优先考虑10+5，如果不行，再考虑5+5+5，如果还不行，那就找零失败。

class Solution
{
public:bool lemonadeChange(vector<int>& bills){int five = 0, ten = 0;for (auto bill : bills){if (bill == 5){five++;}else if (bill == 10){if (five == 0){return false;}five--;ten++;}else{// 贪心，10+5优先于5*3if (five && ten){five--;ten--;}else if (five >= 3){five -= 3;}else{return false;}}}return true;}
};