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

标签: 贪心 数组 排序

难度: Hard

给你一个下标从 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 <= 105
  • transactions[i].length == 2
  • 0 <= costi, cashbacki <= 109

Submission

运行时间: 108 ms

内存: 54.8 MB

class Solution:
    def minimumMoney(self, transactions: List[List[int]]) -> int:
        need = 0
        m = 0
        for c, cb in transactions:
            if c > cb:
                m = max(m, cb)
                need += c - cb 
            else:
                m = max(m, c)
        return m + need

Explain

该题解采用了一个贪心策略，分析所有交易并计算在最坏情况下完成所有交易需要的最少起始资金。它遍历所有交易，如果交易的成本大于返现（c > cb），则意味着你在这笔交易后会亏损 'c - cb' 的金额。因此，累加所有这样的亏损值到 'need' 变量。同时更新 'm' 为所有交易中的 'cb' 的最大值或成本 'c' 的最大值，取决于交易是否产生亏损。最终，你需要的最少起始资金是累积的亏损加上 'm'，这样确保无论交易顺序如何，你都有足够的资金来应对最差情况。

时间复杂度: O(n)

空间复杂度: O(1)

# 添加注释的题解代码

class Solution:
    def minimumMoney(self, transactions: List[List[int]]) -> int:
        need = 0  # 初始化需要的额外资金总和
        m = 0  # 初始化完成交易时所需的最小初始资金
        for c, cb in transactions:  # 遍历每笔交易的成本和返现
            if c > cb:  # 如果成本高于返现
                m = max(m, cb)  # 更新m为迄今为止的最大返现（保证资金足够）
                need += c - cb  # 累加亏损
            else:  # 如果返现高于或等于成本
                m = max(m, c)  # 更新m为迄今为止的最大成本
        return m + need  # 返回初始资金需求，包括额外亏损和最大单笔交易所需资金

Explore

题解中的贪心策略基于假设：在不考虑交易顺序的情况下，确保每次交易后都不导致资金为负。为了满足这一点，我们需要关注两个方面：1）如果成本大于返现的情况，这会导致资金亏损，因此我们累加所有这些亏损值以确保有足够资金覆盖这些亏损。2）独立于亏损，我们还需要考虑单次交易中可能需要的最大资金（无论是成本还是返现）。这样，无论交易顺序如何变化，总能保证有足够的资金来完成所有交易。

在算法中选择最大的返现值或成本值更新`m`是为了确保在最坏的单笔交易情况下，你仍然有足够的资金进行交易。这种策略以最坏情况为准，保证了算法的正确性但有时可能会导致资金的冗余，即可能导致计算出的起始资金比实际需要的多。例如，如果所有交易的返现都非常高，那么实际上并不需要额外准备太多资金来进行交易。

算法通过计算并保留必要的两个最大值：亏损总和和最大单笔交易所需资金（最大成本或返现），来确保交易顺序的灵活性。无论交易的实际执行顺序如何，只要初始资金不少于这两个值的总和，就可以确保始终有足够的资金来应对任何单笔交易以及累积的亏损，从而保持算法的普适性和正确性。

逻辑`c - cb`累加亏损在考虑到最坏情况下总是成立的，因为它保证了在任何交易中，即使没有足够的返现来抵消成本，你也仍然有足够的资金来处理这个亏损。即使后续交易的返现很高，这种方法依然保持有效，因为它是基于确保每笔交易都不会导致资金变为负数的最坏情况分析。这种策略可能导致对资金的过估计，但从安全性角度来看是保守且合理的。