原题链接

贪心

这道题的场景和几年前的我们现实生活中很像，毕竟 2021 年的现在大家都用手机支付了，不过也刚好怀旧一波。

先明确，题目要求我们一开始是没有钱的，全靠老天爷赏饭吃。江山父老能容我 不使人间造孽钱

所以，分为 3 种情况来进行分析：

1. 顾客支付了 5 美元： 直接收下，不用找。
2. 顾客支付了 10 美元： 需要找回 5 元。
3. 顾客支付了 20 美元：需要找回 15元。有两种组合情况，一种是有一张 10 元和一张 5 元，或者三张 5 元。
4. 我们要保证有 10 元先找 10 元，多保留 5 元，这样支付的灵活度更高 (贪心)。

constlemonadeChange=function(bills){letfive=0,ten=0constlen=bills.lengthfor(leti=0;i<len;i++){if(bills[i]==5){five++}elseif(bills[i]==10){if(five==0){returnfalse}five--ten++}elseif(bills[i]==20){if(ten>0&&five>0){ten--five--}elseif(five>=3){five-=3}else{returnfalse}}}returntrue}

• 时间复杂度: O(n)
• 空间复杂度: O(1)