文章

[LeetCode] 每日一题 2412. 完成所有交易的初始最少钱数

题目链接

https://leetcode.cn/problems/minimum-money-required-before-transactions

题目描述

给你一个下标从 0 开始的二维整数数组 transactions,其中transactions[i] = [costi, cashbacki] 。

数组描述了若干笔交易。其中每笔交易必须以 某种顺序 恰好完成一次。在任意一个时刻,你有一定数目的钱 money ,为了完成交易 i ,money >= costi 这个条件必须为真。执行交易后,你的钱数 money 变成 money - costi + cashbacki 

请你返回 任意一种 交易顺序下,你都能完成所有交易的最少钱数 money 是多少。

示例输入

示例 1

输入:transactions = [[2,1],[5,0],[4,2]]
输出:10
解释:
刚开始 money = 10 ,交易可以以任意顺序进行。
可以证明如果 money < 10 ,那么某些交易无法进行。

示例 2

输入:transactions = [[3,0],[0,3]]
输出:3
解释:
- 如果交易执行的顺序是 [[3,0],[0,3]] ,完成所有交易需要的最少钱数是 3 。
- 如果交易执行的顺序是 [[0,3],[3,0]] ,完成所有交易需要的最少钱数是 0 。
所以,刚开始钱数为 3 ,任意顺序下交易都可以全部完成。

提示

  • 1 <= transactions.length <= 10^5

  • transactions[i].length == 2

  • 0 <= costi, cashbacki <= 10^9

解题思路

题目要求在给定一系列交易时,找到完成所有交易所需要的最少初始资金。每笔交易有一个花费(costi)和回报(cashbacki)。每次完成交易后,钱包的余额会减少交易的花费,然后增加回报

关键思路:

  • 我们需要考虑在完成所有交易时,最坏的情况

  • 最坏的情况是先执行所有亏损交易,最终再执行盈利交易,这样可以保证每个时刻的钱足够支付交易

  • 对于每个交易:

    • 如果是亏损交易(即costi > cashbacki),那就需要弥补亏损部分,即costi - cashbacki

    • 如果是盈利交易(即costi <= cashbacki),可以用最小值costi来保证完成该交易

算法步骤:

  1. 遍历所有交易,统计所有亏损交易的总亏损,并记录最小的需要资金(即min(costi, cashbacki)

  2. 最终结果是:初始资金至少为亏损总和和最小需要资金的最大值

代码实现

class Solution {
    public long minimumMoney(int[][] transactions) {
        long costMost = 0;
        int remain = 0;
        for (int[] transaction : transactions) {
            int cost = transaction[0];
            int cashback = transaction[1];
            if (cost > cashback) {
                costMost += (cost - cashback);
            }
            remain = Math.max(remain, Math.min(cost, cashback));
        }
        return costMost + remain;
    }
}

复杂度分析

  • 时间复杂度: O(n),其中 n 是交易的数量。我们只需遍历一次交易数组,进行常数时间的计算

  • 空间复杂度: O(1),只使用了常数级别的额外空间来保存中间结果

总结

这道题虽然标记为困难,但从思路上来看其实并不复杂,核心在于理解最坏情况下所需要的初始资金。最坏情况是,前面都是亏损交易,我们需要保证能够承受这些亏损,并且能够顺利完成剩下的交易。通过贪心算法,我们能够有效地解决这个问题。

在做这题时,我一开始没有注意到数值范围,导致代码出现超限错误。在解决问题时,考虑到不同交易类型的处理方法非常重要。亏损交易和盈利交易的处理方式不同,这也是关键的一步。总的来说,这道题考察了我们对贪心算法的理解和应用,并且通过合理的分析,能够以 O(n) 的时间复杂度解决问题。

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

License:  CC BY 4.0