贪心
解题思路
由题目可知一杯柠檬水的价格是 5$ ，下面模拟不同情况的找零：
- 顾客支付 5$ 时，不需要找零；
- 顾客支付 10$ 时，需要找零 5$ ，没有则无法正确找零；
- 顾客支付 20$ 时，可以找零 10$ 和 5$ 或者三张 5$ 两种方式，由于 5$ 还可以用于找零 支付 10$ 的情况，则为了避免之后无法正确找零，需要优先考虑前面的方案；
局部最优：遇到账单 20$ 则优先消耗美元 10$ 完成本次找零；
全局最优：完成全部账单的找零；
复杂度
-
时间复杂度：
O(N)，其中 N 是 bills 的长度； -
空间复杂度：
O(1)；
代码实现
var lemonadeChange = function (bills) {
let five$ = 0; // 5$ 个数
let ten$ = 0; // 10$ 个数
for (let i = 0; i < bills.length; i++) {
switch (bills[i]) {
case 5:
five$++;
break;
case 10:
if (five$ > 0) {
five$--;
ten$++;
} else {
return false;
}
break;
case 20:
if (ten$ > 0 && five$ > 0) {
five$--;
ten$--;
} else if (five$ >= 3) {
five$ -= 3;
} else {
return false;
}
break;
}
}
return true;
};
参考资料
打赏作者
您的打赏是我前进的动力
微信
支付宝
leetcode🧑💻 135. 分发糖果
上一篇
评论
