860. 柠檬水找零

[Geekhyt]

原题链接

贪心

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

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

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

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

const lemonadeChange = function(bills) {
    let five = 0, ten = 0
    const len = bills.length
    for (let i = 0; i < len; i++) {
        if (bills[i] == 5) {
            five++
        } else if (bills[i] == 10) {
            if (five == 0) {
                return false
            }
            five--
            ten++
        } else if (bills[i] == 20) {
            if (ten > 0 && five > 0) {
                ten--
                five--
            } else if (five >= 3) {
                five -= 3
            } else {
                return false
            }
        }
    }
    return true
}

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