柠檬水找零

Leetcode Link: 860. 柠檬水找零 - 力扣（LeetCode）

题目

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

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

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

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

解法一

思路：贪心，如果每次需要找钱，需要每次都找面值尽可能大的，因为5块可以凑成10块，但是10块没法拆成俩5块的。

题解：

class Solution:
    def lemonadeChange(self, bills: List[int]) -> bool:
	    # 开始口袋空空
        money = {5:0, 10:0, 20:0}
        for give in bills:
            if give == 5:    # 5块不着钱
                money[5] += 1
            elif give == 10:  # 10块找5块
                money[10] += 1
                if money[5] > 0:
                    money[5] -= 1
                else:
                    return False
            elif give == 20: # 20块先找10+5，不行再找5+5+5
                money[20] += 1
                if money[10] > 0 and money[5] > 0:
                    money[10] -= 1
                    money[5] -= 1
                elif money[5] >= 3:
                    money[5] -= 3
                else:
                    return False
        return True