0860. 柠檬水找零 #
- 标签:贪心、数组
- 难度:简单
题目大意 #
描述:一杯柠檬水的售价是 $5$ 美元。现在有 $n$ 个顾客排队购买柠檬水,每人只能购买一杯。顾客支付的钱面额有 $5$ 美元、$10$ 美元、$20$ 美元。必须给每个顾客正确找零(就是每位顾客需要向你支付 $5$ 美元,多出的钱要找还回顾客)。
现在给定 $n$ 个顾客支付的钱币面额数组 bills
。
要求:如果能给每位顾客正确找零,则返回 True
,否则返回 False
。
说明:
- 一开始的时候手头没有任何零钱。
- $1 \le bills.length \le 10^5$。
bills[i]
不是 $5$ 就是 $10$ 或是 $20$。
示例:
- 示例 1:
|
|
- 示例 2:
|
|
解题思路 #
思路 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:复杂度分析 #
- 时间复杂度:$O(n)$,其中 $n$ 是数组
bill
的长度。 - 空间复杂度:$O(1)$。