Medium

题目描述

有一台 ATM 机器，存储着 5 种面额的钞票：20、50、100、200 和 500 美元。最初 ATM 是空的。用户可以使用机器来存钱或取钱。

取钱时，机器优先使用较大面额的钞票。

  • 例如，如果你想取 300 美元，有 2 张 50 美元钞票、1 张 100 美元钞票和 1 张 200 美元钞票，那么机器将使用 100 美元和 200 美元的钞票。
  • 但是，如果你想取 600 美元，有 3 张 200 美元钞票和 1 张 500 美元钞票，那么取钱请求将被拒绝，因为机器将首先尝试使用 500 美元钞票，然后无法使用钞票来完成剩余的 100 美元。注意机器不允许使用 200 美元钞票来代替 500 美元钞票。

实现 ATM 类：

  • ATM() 初始化 ATM 对象。
  • void deposit(int[] banknotesCount) 按照 20、50、100、200 和 500 美元的顺序存入新的钞票。
  • int[] withdraw(int amount) 返回长度为 5 的数组，表示按照 20、50、100、200 和 500 美元的顺序交给用户的钞票数量，并在取钱后更新 ATM 中的钞票数量。如果无法取钱则返回 [-1]（在这种情况下不要取出任何钞票）。

示例 1:

输入
["ATM", "deposit", "withdraw", "deposit", "withdraw", "withdraw"]
[[], [[0,0,1,2,1]], [600], [[0,1,0,1,1]], [600], [550]]
输出
[null, null, [0,0,1,0,1], null, [-1], [0,1,0,0,1]]

解释
ATM atm = new ATM();
atm.deposit([0,0,1,2,1]); // 存入 1 张 100 美元钞票，2 张 200 美元钞票，1 张 500 美元钞票
atm.withdraw(600);        // 返回 [0,0,1,0,1]。机器使用 1 张 100 美元钞票和 1 张 500 美元钞票
atm.deposit([0,1,0,1,1]); // 存入 1 张 50 美元、200 美元和 500 美元钞票
atm.withdraw(600);        // 返回 [-1]。机器尝试使用 500 美元钞票，然后无法完成剩余的 100 美元
atm.withdraw(550);        // 返回 [0,1,0,0,1]。机器使用 1 张 50 美元钞票和 1 张 500 美元钞票

约束条件:

  • banknotesCount.length == 5
  • 0 <= banknotesCount[i] <= 10^9
  • 1 <= amount <= 10^9
  • 总共最多调用 5000 次 withdraw 和 deposit
  • 每个函数 withdraw 和 deposit 至少被调用一次
  • 所有存款中 banknotesCount[i] 的总和不超过 10^9

解题思路

这道题的关键是理解ATM机器的工作机制：优先使用大面额钞票进行取钱操作。

核心思路：

  1. 数据存储：使用数组存储每种面额的钞票数量，索引对应关系为：[20, 50, 100, 200, 500]

  2. 存钱操作：简单地将存入的钞票数量加到对应的存储数组中

  3. 取钱操作（贪心算法）：

    • 从最大面额开始，尽可能多地使用当前面额的钞票
    • 对于每种面额，计算最多能使用多少张：min(需要的张数, 库存张数)
    • 更新剩余金额，继续处理下一个面额
    • 如果最终剩余金额不为0，说明无法精确找零，返回[-1]

  4. 状态回滚：在取钱失败时，需要保证ATM状态不被修改，所以先在副本上模拟操作

算法流程：

  • 创建当前库存的副本进行模拟
  • 从500美元开始，依次尝试使用每种面额
  • 计算当前面额最多能用多少张：min(amount / 面额值, 当前库存)
  • 更新剩余金额和使用的钞票数
  • 如果最终能够精确找零，更新真实库存并返回结果
  • 否则返回[-1]

这种贪心策略是最优的，因为题目明确要求优先使用大面额钞票。

代码实现

class ATM {
private:
    vector<long long> count;
    vector<int> values;
    
public:
    ATM() {
        count = vector<long long>(5, 0);
        values = {20, 50, 100, 200, 500};
    }
    
    void deposit(vector<int> banknotesCount) {
        for (int i = 0; i < 5; i++) {
            count[i] += banknotesCount[i];
        }
    }
    
    vector<int> withdraw(int amount) {
        vector<int> result(5, 0);
        vector<long long> tempCount = count;
        
        for (int i = 4; i >= 0; i--) {
            if (tempCount[i] > 0 && amount >= values[i]) {
                int needed = amount / values[i];
                int used = min((long long)needed, tempCount[i]);
                result[i] = used;
                amount -= used * values[i];
                tempCount[i] -= used;
            }
        }
        
        if (amount == 0) {
            count = tempCount;
            return result;
        }
        
        return {-1};
    }
};

class ATM:

    def __init__(self):
        self.count = [0] * 5
        self.values = [20, 50, 100, 200, 500]

    def deposit(self, banknotesCount):
        for i in range(5):
            self.count[i] += banknotesCount[i]

    def withdraw(self, amount):
        result = [0] * 5
        temp_count = self.count[:]
        
        for i in range(4, -1, -1):
            if temp_count[i] > 0 and amount >= self.values[i]:
                needed = amount // self.values[i]
                used = min(needed, temp_count[i])
                result[i] = used
                amount -= used * self.values[i]
                temp_count[i] -= used
        
        if amount == 0:
            self.count = temp_count
            return result
        
        return [-1]

public class ATM {
    private long[] count;
    private int[] values;

    public ATM() {
        count = new long[5];
        values = new int[] {20, 50, 100, 200, 500};
    }
    
    public void Deposit(int[] banknotesCount) {
        for (int i = 0; i < 5; i++) {
            count[i] += banknotesCount[i];
        }
    }
    
    public int[] Withdraw(int amount) {
        int[] result = new int[5];
        long[] tempCount = new long[5];
        Array.Copy(count, tempCount, 5);
        
        for (int i = 4; i >= 0; i--) {
            if (tempCount[i] > 0 && amount >= values[i]) {
                int needed = amount / values[i];
                long used = Math.Min(needed, tempCount[i]);
                result[i] = (int)used;
                amount -= (int)used * values[i];
                tempCount[i] -= used;
            }
        }
        
        if (amount == 0) {
            Array.Copy(tempCount, count, 5);
            return result;
        }
        
        return new int[] {-1};
    }
}

var ATM = function() {
    this.banknotes = [0, 0, 0, 0, 0];
    this.values = [20, 50, 100, 200, 500];
};

ATM.prototype.deposit = function(banknotesCount) {
    for (let i = 0; i < 5; i++) {
        this.banknotes[i] += banknotesCount[i];
    }
};

ATM.prototype.withdraw = function(amount) {
    let result = [0, 0, 0, 0, 0];
    let remaining = amount;
    
    for (let i = 4; i >= 0; i--) {
        let count = Math.min(Math.floor(remaining / this.values[i]), this.banknotes[i]);
        result[i] = count;
        remaining -= count * this.values[i];
    }
    
    if (remaining > 0) {
        return [-1];
    }
    
    for (let i = 0; i < 5; i++) {
        this.banknotes[i] -= result[i];
    }
    
    return result;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

操作时间复杂度空间复杂度
depositO(1)O(1)
withdrawO(1)O(1)

说明：

  • 时间复杂度：所有操作都是对固定大小的数组（长度为5）进行操作，因此时间复杂度为O(1)
  • 空间复杂度：只使用了固定大小的额外空间来存储钞票数量和临时数组，空间复杂度为O(1)

相关题目