0860. 柠檬水找零 #

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

题目大意 #

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

现在给定 $n$ 个顾客支付的钱币面额数组 bills。

要求：如果能给每位顾客正确找零，则返回 True，否则返回 False。

说明：

一开始的时候手头没有任何零钱。
$1 \le bills.length \le 10^5$。
bills[i] 不是 $5$ 就是 $10$ 或是 $20$。

示例：

示例 1：

1
2
3
4
5
6
7


输入：bills = [5,5,5,10,20]
输出：True
解释：
前 3 位顾客那里，我们按顺序收取 3 张 5 美元的钞票。
第 4 位顾客那里，我们收取一张 10 美元的钞票，并返还 5 美元。
第 5 位顾客那里，我们找还一张 10 美元的钞票和一张 5 美元的钞票。
由于所有客户都得到了正确的找零，所以我们输出 True。

示例 2：

1
2
3
4
5
6
7


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

解题思路 #

思路 1：贪心算法 #

由于顾客只能给我们 $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：代码 #

 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

思路 1：复杂度分析 #

时间复杂度：$O(n)$，其中 $n$ 是数组 bill 的长度。
空间复杂度：$O(1)$。