2412. 交易前所需的最少资金

Hard

题目描述

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

该数组描述了一些交易，每个交易必须按某个顺序恰好完成一次。在任何时刻，你都有一定数量的资金。为了完成交易 i，必须满足 money >= costi。执行交易后，money 变为 money - costi + cashbacki。

返回在任何交易顺序下都能完成所有交易所需的最少初始资金。

示例 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。
因此，从 money = 3 开始，可以按任何顺序执行交易。

约束：

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

解题思路

这道题的核心思想是将交易分为两类：盈利交易（cashback >= cost）和亏损交易（cashback < cost），然后分别考虑最优的执行顺序。

分析思路：

交易分类：
- 盈利交易：cashback >= cost，执行后资金增加或不变
- 亏损交易：cashback < cost，执行后资金减少
盈利交易的最优顺序：
- 由于盈利交易最终会增加资金，我们希望尽早获得资金增益
- 按照 cost 降序排列，先做成本高的交易，这样能尽早满足后续交易的资金要求
亏损交易的最优顺序：
- 亏损交易会减少资金，我们希望尽可能保留更多资金
- 按照 cashback 升序排列，先做返现少的交易，这样能保留更多资金用于后续交易
计算最少初始资金：
- 遍历所有交易，跟踪当前所需的最少资金
- 对于每个交易，当前资金必须 >= cost，然后更新资金为 money - cost + cashback
- 记录过程中需要的最大资金量

这种贪心策略确保了无论以什么顺序执行交易，初始资金都足够完成所有操作。

代码实现

class Solution {
public:
    long long minimumMoney(vector<vector<int>>& transactions) {
        vector<vector<int>> profit, loss;
        
        // 分类交易
        for (auto& t : transactions) {
            if (t[1] >= t[0]) {
                profit.push_back(t);
            } else {
                loss.push_back(t);
            }
        }
        
        // 盈利交易按cost降序排列
        sort(profit.begin(), profit.end(), [](const vector<int>& a, const vector<int>& b) {
            return a[0] > b[0];
        });
        
        // 亏损交易按cashback升序排列
        sort(loss.begin(), loss.end(), [](const vector<int>& a, const vector<int>& b) {
            return a[1] < b[1];
        });
        
        long long money = 0, maxMoney = 0;
        
        // 处理盈利交易
        for (auto& t : profit) {
            maxMoney = max(maxMoney, money + t[0]);
            money += t[1] - t[0];
        }
        
        // 处理亏损交易
        for (auto& t : loss) {
            maxMoney = max(maxMoney, money + t[0]);
            money += t[1] - t[0];
        }
        
        return maxMoney;
    }
};

class Solution:
    def minimumMoney(self, transactions: List[List[int]]) -> int:
        profit = []
        loss = []
        
        # 分类交易
        for cost, cashback in transactions:
            if cashback >= cost:
                profit.append([cost, cashback])
            else:
                loss.append([cost, cashback])
        
        # 盈利交易按cost降序排列
        profit.sort(key=lambda x: x[0], reverse=True)
        
        # 亏损交易按cashback升序排列
        loss.sort(key=lambda x: x[1])
        
        money = 0
        max_money = 0
        
        # 处理盈利交易
        for cost, cashback in profit:
            max_money = max(max_money, money + cost)
            money += cashback - cost
        
        # 处理亏损交易
        for cost, cashback in loss:
            max_money = max(max_money, money + cost)
            money += cashback - cost
        
        return max_money

public class Solution {
    public long MinimumMoney(int[][] transactions) {
        var profit = new List<int[]>();
        var loss = new List<int[]>();
        
        // 分类交易
        foreach (var t in transactions) {
            if (t[1] >= t[0]) {
                profit.Add(t);
            } else {
                loss.Add(t);
            }
        }
        
        // 盈利交易按cost降序排列
        profit.Sort((a, b) => b[0].CompareTo(a[0]));
        
        // 亏损交易按cashback升序排列
        loss.Sort((a, b) => a[1].CompareTo(b[1]));
        
        long money = 0, maxMoney = 0;
        
        // 处理盈利交易
        foreach (var t in profit) {
            maxMoney = Math.Max(maxMoney, money + t[0]);
            money += t[1] - t[0];
        }
        
        // 处理亏损交易
        foreach (var t in loss) {
            maxMoney = Math.Max(maxMoney, money + t[0]);
            money += t[1] - t[0];
        }
        
        return maxMoney;
    }
}

var minimumMoney = function(transactions) {
    const profit = [];
    const loss = [];
    
    // 分类交易
    for (const [cost, cashback] of transactions) {
        if (cashback >= cost) {
            profit.push([cost, cashback]);
        } else {
            loss.push([cost, cashback]);
        }
    }
    
    // 盈利交易按cost降序排列
    profit.sort((a, b) => b[0] - a[0]);
    
    // 亏损交易按cashback升序排列
    loss.sort((a, b) => a[1] - b[1]);
    
    let money = 0;
    let maxMoney = 0;
    
    // 处理盈利交易
    for (const [cost, cashback] of profit) {
        maxMoney = Math.max(maxMoney, money + cost);
        money += cashback - cost;
    }
    
    // 处理亏损交易
    for (const [cost, cashback] of loss) {
        maxMoney = Math.max(maxMoney, money + cost);
        money += cashback - cost;
    }
    
    return maxMoney;
};

在 LeetCode 上运行：力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型	值
时间复杂度	O(n log n)
空间复杂度	O(n)

说明：

时间复杂度：主要消耗在排序操作上，需要对两类交易分别排序，每次排序的时间复杂度为 O(n log n)
空间复杂度：需要额外的数组来存储分类后的交易，最坏情况下需要 O(n) 的空间

题目描述#

解题思路#

代码实现#

复杂度分析#

题目描述

解题思路

代码实现

复杂度分析