[LeetCode] 每日一题 2241. 设计一个 ATM 机器

题目链接

https://leetcode.cn/problems/design-an-atm-machine/

题目描述

一个 ATM 机器，存有 5 种面值的钞票：20 ，50 ，100 ，200 和 500 美元。初始时，ATM 机是空的。用户可以用它存或者取任意数目的钱。

取款时，机器会优先取 较大 数额的钱。

• 比方说，你想取 $300 ，并且机器里有 2 张 $50 的钞票，1 张 $100 的钞票和1 张 $200 的钞票，那么机器会取出 $100 和 $200 的钞票。

• 但是，如果你想取 $600 ，机器里有 3 张 $200 的钞票和1 张 $500 的钞票，那么取款请求会被拒绝，因为机器会先取出 $500 的钞票，然后无法取出剩余的 $100 。注意，因为有 $500 钞票的存在，机器 不能 取 $200 的钞票。

请你实现 ATM 类：

• ATM() 初始化 ATM 对象。

• void deposit(int[] banknotesCount) 分别存入 $20 ，$50，$100，$200 和 $500 钞票的数目。

• int[] withdraw(int amount) 返回一个长度为 5 的数组，分别表示 $20 ，$50，$100 ，$200 和 $500 钞票的数目，并且更新 ATM 机里取款后钞票的剩余数量。如果无法取出指定数额的钱，请返回 [-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 的钞票。机器里剩余钞票的数量为 [0,0,0,2,0] 。
atm.deposit([0,1,0,1,1]); // 存入 1 张 $50 ，1 张 $200 和 1 张 $500 的钞票。
                          // 机器中剩余钞票数量为 [0,1,0,3,1] 。
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 至少各有 一次 调用。

题解

解题思路

这道题需要实现一个模拟 ATM 机器存款和取款的功能。核心难点在于取款时需要按题意规则优先使用大面额的钞票，同时如果无法满足指定金额的取款需求，需要撤回操作，将取款前的状态还原

1. 存款操作
   存款非常简单，直接将输入的钞票数量累加到机器内部的存储数组中即可

2. 取款操作
   取款时从大面额钞票开始尝试取钱：

   • 首先计算当前面额的钞票最多可以取的数量（当前金额除以面额值，并取钞票数量和剩余钞票数量的最小值）

   • 更新取款记录并减少 ATM 内部对应钞票的数量

   • 减少剩余需要取出的金额

   如果最终金额未能完全取出，则说明取款失败，需将先前减少的钞票还原，并返回 [-1]

代码实现

class ATM {
    private final int[] value = {20, 50, 100, 200, 500}; // 钞票面额
    private final int[] cnt = new int[5]; // 每种面额钞票的数量

    public ATM() {
    }

    public void deposit(int[] banknotesCount) {
        for (int i = 0; i < 5; i++) {
            cnt[i] += banknotesCount[i];
        }
    }

    public int[] withdraw(int amount) {
        int[] ans = new int[5]; // 暂存每种面额取出的数量
        for (int i = 4; amount > 0 && i >= 0; i--) { // 从大面额开始尝试取钱
            if (cnt[i] == 0 || value[i] > amount) {
                continue; // 跳过当前面额
            }
            ans[i] = Math.min(amount / value[i], cnt[i]); // 当前面额最多能取的张数
            cnt[i] -= ans[i]; // 更新 ATM 内部存储
            amount -= ans[i] * value[i]; // 减少待取金额
        }

        if (amount != 0) {
            // 还原钞票数量
            for (int i = 0; i < 5; i++) {
                cnt[i] += ans[i]; 
            }
            return new int[] {-1};
        }
        return ans;
    }
}

复杂度分析

1. 存款操作

   • 时间复杂度：O(1)，只需对 5 种钞票数量进行更新

   • 空间复杂度：O(1)，不需要额外空间

2. 取款操作

   • 时间复杂度：O(1)，最多需要遍历 5 种面额的钞票

   • 空间复杂度：O(1)，仅使用一个长度为 5 的数组存储结果

综合来看，整体的时间复杂度和空间复杂度均为常数级别

总结

这道题主要考察了对模拟问题的理解和实现能力。通过优先从大面额开始取款，我们能够满足尽量少张数取钱的需求。同时，处理无法取款的场景时需要谨慎，确保 ATM 内部状态的还原

在实现过程中需要特别注意以下几点：

• 从大面额到小面额依次取钱，符合题意要求

• 取款失败时需要回滚取款操作，确保状态一致性

• 注意边界情况，如取款金额为 0 或 ATM 机中没有钞票等

希望这篇分享能为你带来启发！如果你有任何问题或建议，欢迎在评论区留言，与我共同交流探讨。