2023年7月22日每日一题--860. 柠檬水找零

leetcode链接：
860. 柠檬水找零

题目分析

先暴力求解来一波。

方案一

暴力求解，问题解决，

class Solution {
    public boolean lemonadeChange(int[] bills) {
        int[] money = new int[]{0, 0}; // 两位，只记录5元和10元，20元不记录
        for (int i = 0; i < bills.length; i++) {
            if (bills[i] == 5) {
                money[0] += 1;
            } else if (bills[i] == 10) {
                money[0] -= 1;
                money[1] += 1;
                if (money[0] < 0) {
                    return false;
                }
            } else {
                if (money[1] > 0) {
                    money[0] -= 1;
                    money[1] -= 1;
                    if (money[0] < 0) {
                        return false;
                    }
                } else {
                    money[0] -= 3;
                    if (money[0] < 0) {
                        return false;
                    }
                }
            }
        }
        return true;
    }
}

结果

解答成功:
执行耗时:2 ms,击败了62.30% 的Java用户
内存消耗:55.5 MB,击败了23.03% 的Java用户

分析

时间复杂度：
O( n )

空间复杂度：
O( 1 )

官方题解

https://leetcode.cn/problems/lemonade-change/solution/ning-meng-shui-zhao-ling-by-leetcode-sol-nvp7/、

这里的贪心就在于：面对20元找零时，优先用掉10元面额的

class Solution {
    public boolean lemonadeChange(int[] bills) {
        int five = 0, ten = 0;
        for (int bill : bills) {
            if (bill == 5) {
                five++;
            } else if (bill == 10) {
                if (five == 0) {
                    return false;
                }
                five--;
                ten++;
            } else {
                if (five > 0 && ten > 0) {
                    five--;
                    ten--;
                } else if (five >= 3) {
                    five -= 3;
                } else {
                    return false;
                }
            }
        }
        return true;
    }
}

作者：LeetCode-Solution
链接：https://leetcode.cn/problems/lemonade-change/solution/ning-meng-shui-zhao-ling-by-leetcode-sol-nvp7/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。