[LeetCode] 每日一题 2412. 完成所有交易的初始最少钱数
题目链接
题目描述
给你一个下标从 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
来保证完成该交易
算法步骤:
遍历所有交易,统计所有亏损交易的总亏损,并记录最小的需要资金(即
min(costi, cashbacki)
)最终结果是:初始资金至少为亏损总和和最小需要资金的最大值
代码实现
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) 的时间复杂度解决问题。
希望这篇分享能为你带来启发!如果你有任何问题或建议,欢迎在评论区留言,与我共同交流探讨。