860. 柠檬水找零
题目描述
柠檬水每杯卖 5 美元。顾客按数组 bills 的顺序依次购买，每人只买一杯，付的是一张 5、10 或 20 美元的钞票。
你开始时手里没有任何零钱，只能用之前收到的钞票找零。每位顾客都必须恰好找回多付的钱，使其实际只付 5 美元。
如果能给所有顾客都正确找零，返回 true，否则返回 false。
示例 1
输入：bills = [5,5,5,10,20] 输出：true
解释：前三人付 5；第四人付 10 找回 5；第五人付 20 找回 10 和 5。
示例 2
输入：bills = [5,5,10,10,20] 输出：false
解释：最后一位付 20 时手里只有两张 10，凑不出 15。
数据范围
1 <= bills.length <= 10^5bills[i]只会是5、10或20。
解题思路
只有 5 元和 10 元能用来找零，所以只记录这两种纸币的张数。收 5 元不用找；收 10 元必须找一张 5 元；收 20 元要找 15 元，有两种方式：10+5 或 5+5+5。贪心地优先用 10+5，因为 10 元只能在找 20 元时用上，而 5 元对 10 元和 20 元都有用，应该尽量留着。
为什么正确
five 和 ten 始终是钱箱里 5 元、10 元的张数；在所有可行的找零方式中，优先 10+5 能让剩下的 5 元最多。
复杂度分析
时间 O(n)，额外空间 O(1)。
易错点
收 20 元时先用三张 5 元找零。这样会把万能的 5 元提前用光，后面的 10 元顾客就找不开了。
参考代码
Python、Java、C++、Go、JavaScript、TypeScript 六种语言，逻辑一致。
class Solution:
def lemonadeChange(self, bills: List[int]) -> bool:
five = ten = 0
for b in bills:
if b == 5:
five += 1
elif b == 10:
if five == 0:
return False
five -= 1
ten += 1
elif ten > 0 and five > 0:
ten -= 1
five -= 1
elif five >= 3:
five -= 3
else:
return False
return Trueclass Solution {
public boolean lemonadeChange(int[] bills) {
int five = 0, ten = 0;
for (int b : bills) {
if (b == 5) {
five++;
} else if (b == 10) {
if (five == 0) {
return false;
}
five--;
ten++;
} else if (ten > 0 && five > 0) {
ten--;
five--;
} else if (five >= 3) {
five -= 3;
} else {
return false;
}
}
return true;
}
}class Solution {
public:
bool lemonadeChange(vector<int>& bills) {
int five = 0, ten = 0;
for (int b : bills) {
if (b == 5) {
five++;
} else if (b == 10) {
if (five == 0) {
return false;
}
five--;
ten++;
} else if (ten > 0 && five > 0) {
ten--;
five--;
} else if (five >= 3) {
five -= 3;
} else {
return false;
}
}
return true;
}
};func lemonadeChange(bills []int) bool {
five, ten := 0, 0
for _, b := range bills {
if b == 5 {
five++
} else if b == 10 {
if five == 0 {
return false
}
five--
ten++
} else if ten > 0 && five > 0 {
ten--
five--
} else if five >= 3 {
five -= 3
} else {
return false
}
}
return true
}var lemonadeChange = function(bills) {
let five = 0, ten = 0;
for (const b of bills) {
if (b === 5) {
five++;
} else if (b === 10) {
if (five === 0) {
return false;
}
five--;
ten++;
} else if (ten > 0 && five > 0) {
ten--;
five--;
} else if (five >= 3) {
five -= 3;
} else {
return false;
}
}
return true;
};function lemonadeChange(bills: number[]): boolean {
let five = 0, ten = 0;
for (const b of bills) {
if (b === 5) {
five++;
} else if (b === 10) {
if (five === 0) {
return false;
}
five--;
ten++;
} else if (ten > 0 && five > 0) {
ten--;
five--;
} else if (five >= 3) {
five -= 3;
} else {
return false;
}
}
return true;
}