在柠檬水摊上,每一杯柠檬水的售价为 5
美元。顾客排队购买你的产品,(按账单 bills
支付的顺序)一次购买一杯。
每位顾客只买一杯柠檬水,然后向你付 5
美元、10
美元或 20
美元。你必须给每个顾客正确找零,也就是说净交易是每位顾客向你支付 5
美元。
注意,一开始你手头没有任何零钱。
给你一个整数数组 bills
,其中 bills[i]
是第 i
位顾客付的账。如果你能给每位顾客正确找零,返回 true
,否则返回 false
。
示例 1:
输入:bills = [5,5,5,10,20] 输出:true 解释: 前 3 位顾客那里,我们按顺序收取 3 张 5 美元的钞票。 第 4 位顾客那里,我们收取一张 10 美元的钞票,并返还 5 美元。 第 5 位顾客那里,我们找还一张 10 美元的钞票和一张 5 美元的钞票。 由于所有客户都得到了正确的找零,所以我们输出 true。
示例 2:
输入:bills = [5,5,10,10,20] 输出:false 解释: 前 2 位顾客那里,我们按顺序收取 2 张 5 美元的钞票。 对于接下来的 2 位顾客,我们收取一张 10 美元的钞票,然后返还 5 美元。 对于最后一位顾客,我们无法退回 15 美元,因为我们现在只有两张 10 美元的钞票。 由于不是每位顾客都得到了正确的找零,所以答案是 false。
提示:
1 <= bills.length <= 105
bills[i]
不是5
就是10
或是20
方法一:贪心 + 模拟
从前往后遍历账单数组 bills
,如果当前账单是 5 美元,那么直接收下即可;如果当前账单是 10 美元,那么需要找零 5 美元;如果当前账单是 20 美元,那么需要找零 15 美元,此时有两种找零方式:找零 1 张 10 美元 + 1 张 5 美元;找零 3 张 5 美元。如果找零失败,直接返回 false
。
时间复杂度 bills
的长度。
class Solution:
def lemonadeChange(self, bills: List[int]) -> bool:
five = ten = 0
for v in bills:
if v == 5:
five += 1
elif v == 10:
ten += 1
five -= 1
else:
if ten:
ten -= 1
five -= 1
else:
five -= 3
if five < 0:
return False
return True
class Solution {
public boolean lemonadeChange(int[] bills) {
int five = 0, ten = 0;
for (int v : bills) {
if (v == 5) {
++five;
} else if (v == 10) {
++ten;
--five;
} else {
if (ten > 0) {
--ten;
--five;
} else {
five -= 3;
}
}
if (five < 0) {
return false;
}
}
return true;
}
}
class Solution {
public:
bool lemonadeChange(vector<int>& bills) {
int five = 0, ten = 0;
for (int v : bills) {
if (v == 5)
++five;
else if (v == 10) {
++ten;
--five;
} else {
if (ten)
--ten, --five;
else
five -= 3;
}
if (five < 0) return false;
}
return true;
}
};
func lemonadeChange(bills []int) bool {
five, ten := 0, 0
for _, v := range bills {
if v == 5 {
five++
} else if v == 10 {
ten++
five--
} else {
if ten > 0 {
ten--
five--
} else {
five -= 3
}
}
if five < 0 {
return false
}
}
return true
}
function lemonadeChange(bills: number[]): boolean {
let five = 0;
let ten = 0;
for (let bill of bills) {
switch (bill) {
case 5:
five++;
break;
case 10:
five--;
ten++;
break;
case 20:
if (ten !== 0) {
ten -= 1;
bill -= 10;
}
five -= bill / 5 - 1;
break;
}
if (five < 0) {
return false;
}
}
return true;
}
impl Solution {
pub fn lemonade_change(bills: Vec<i32>) -> bool {
let (mut five, mut ten) = (0, 0);
for bill in bills.iter() {
match bill {
5 => {
five += 1;
}
10 => {
five -= 1;
ten += 1;
}
_ => {
if ten != 0 {
ten -= 1;
five -= 1;
} else {
five -= 3;
}
}
}
if five < 0 {
return false;
}
}
true
}
}