【力扣每日一题】LeetCode 2412: 完成所有交易的初始最少钱数

LeetCode 2412: 完成所有交易的初始最少钱数

题目解析

问题描述

给定一个二维数组 transactions，每个元素 transactions[i] = [costi, cashbacki] 表示一个交易。对于每笔交易，要求你完成该交易时有足够的初始资金 money，并且交易会减少或增加你账户中的资金。具体地，交易的费用为 costi，交易后的现金返还为 cashbacki。执行交易后，money 会变成 money - costi + cashbacki。

你的目标是找到完成所有交易所需的最少初始资金 money，确保你在任意顺序下都能完成所有交易。

示例

示例 1
输入：

transactions = [[2,1], [5,0], [4,2]]

输出：

解释：
若初始资金为 10，那么无论以何种顺序执行交易，都能成功完成所有交易。

示例 2
输入：

transactions = [[3,0], [0,3]]

输出：

解释：
若初始资金为 3，无论以何种顺序执行交易，都能完成所有交易。具体地，执行顺序为 [[3,0], [0,3]] 时，资金为 3，完成所有交易。

提示

1 <= transactions.length <= 10^5
transactions[i].length == 2
0 <= costi, cashbacki <= 10^9

思路分析

分析问题

本题的关键在于找出一个足够的初始资金 money，使得无论交易顺序如何，都能够完成所有交易。我们可以将问题分为两部分来分析：

资金不足部分：对于每笔交易，money 需要保证至少能支付 costi。因此，在每笔交易中，若 costi > cashbacki，则至少需要支付 costi - cashbacki 的差额，这部分差额累计起来即为必须的最小资金。
最小起始资金：对于每一笔交易，它可能会有一部分“返还资金”（即 cashbacki）。对于完成某些交易，cashbacki 可以帮助你减轻初始资金的压力。我们需要找出一个最合适的初始资金，使得所有交易都能顺利进行。

解题思路

首先计算每笔交易的资金缺口：对于每笔交易 i = [costi, cashbacki]，我们需要额外的资金 max(0, costi - cashbacki) 才能顺利完成该交易。
找到最大需要的初始资金：通过找出所有交易中的最小金额 min(costi, cashbacki)，这个值表示为了完成所有交易，你在最初时刻可能需要的最大额外资金。
返回结果：最终的初始资金应该是上面两者的总和。

具体实现

from typing import Listclass Solution:def minimumMoney(self, transactions: List[List[int]]) -> int:# total 为所有交易的资金缺口total = 0# mx 为所有交易中最小的 costi 和 cashbacki 的差额mx = 0# 遍历每一笔交易for cost, cashback in transactions:# 累加每笔交易的资金缺口total += max(0, cost - cashback)# 找到最大需要的起始资金mx = max(mx, min(cost, cashback))# 最终的初始资金 = 所有交易的资金缺口 + 最大需要的起始资金return total + mx

代码解析

total：累加所有交易中必须先支付的资金缺口（即 max(0, cost - cashback)）。这表示即使你按照最优顺序进行交易，至少也需要这么多资金才能顺利完成所有交易。
mx：计算所有交易中的最大 min(costi, cashbacki)，这代表了为了保证所有交易顺利完成，在最开始时可能需要的额外资金。

最终返回的结果是 total + mx，即所有交易的资金缺口和最大额外资金的和。

复杂度分析

时间复杂度：
遍历一次 transactions 数组，每次操作常数时间，因此时间复杂度是 O(n)，其中 n 是 transactions 的长度。
空间复杂度：
使用了常数空间来存储一些变量，因此空间复杂度是 O(1)。

总结

通过这个问题，我们可以学习到如何通过分解交易中的不同部分来分析最小初始资金。理解了如何计算资金缺口和最小需要的额外资金后，可以高效地得出最少初始资金。这个方法适用于交易顺序不确定的情况下，保证无论如何都能顺利完成所有交易。