0860. 柠檬水找零 #

标签：贪心、数组
难度：简单

题目大意 #

一杯柠檬水的售价是 5 美元。现在有 N 个顾客排队购买柠檬水，每人只能购买一杯。顾客支付的钱面额有 5 美元、10 美元、20 美元。必须给每个顾客正确找零（就是每位顾客需要向你支付 5 美元，多出的钱要找还回顾客）。

现在给定 N 个顾客支付的钱币面额数组 bills，如果能给每位顾客正确找零，则返回 True，否则返回 False。

注意：一开始的时候手头没有任何零钱。

解题思路 #

由于顾客只能给我们 5、10、20 三种面额的钞票，且一开始我们手头没有任何钞票，所以我们手中所能拥有的钞票面额只能是 5、10、20。因此可以采取下面的策略。

如果顾客支付 5 美元，直接收下。
如果顾客支付 10 美元，如果我们手头有 5 美元面额的钞票，则找给顾客，否则无法正确找零，返回 False。
如果顾客支付 20 美元，如果我们手头有 1 张 10 美元和 1 张 5 美元的钞票，或者有 3 张 5 美元的钞票，则可以找给顾客。如果两种组合方式同时存在，倾向于第 1 种方式找零，因为使用 5 美元的场景比使用 10 美元的场景多，要尽可能的保留 5 美元的钞票。如果这两种组合方式都不通知，则无法正确找零，返回 False。

所以，我们使用 five 和 ten 来维护手中 5 美元、10 美团的钞票数量，然后遍历一遍根据上述条件分别判断即可。

代码 #

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23


class Solution:
    def lemonadeChange(self, bills: List[int]) -> bool:
        five, ten, twenty = 0, 0, 0
        for bill in bills:
            if bill == 5:
                five += 1
            if bill == 10:
                if five <= 0:
                    return False
                ten += 1
                five -= 1
            if bill == 20:
                if five > 0 and ten > 0:
                    five -= 1
                    ten -= 1
                    twenty += 1
                elif five >= 3:
                    five -= 3
                    twenty += 1
                else:
                    return False

        return True