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 <= 105
• transactions[i].length == 2
• 0 <= costi, cashbacki <= 109

视频讲解 已出炉，欢迎点赞三连，在评论区分享你对这场双周赛的看法~

---

提示 1

考虑最坏情况，即先亏钱（cost}>\textit{cashback），再赚钱。

记 totalLose 为亏钱下的所有 cost}-\textit{cashback 之和。

提示 2

如何最大化初始 money ？

枚举所有交易，分类讨论：

• 对于 cost}_i\le\textit{cashback}_i 的交易，这笔交易可以发生在亏钱后，此时初始 money}=\textit{totalLose}+\textit{cost}_i；
• 对于 cost}_i>\textit{cashback}_i 的交易，这笔交易可以发生在最后一笔亏钱时，由于已经计入 totalLose 中，需要从 totalLose 中减去 cost}_i-\textit{cashback}_i，再加上 cost}_i，化简得到初始 money}=\textit{totalLose}+\textit{cashback}_i。

取所有初始 money 的最大值，即为答案。

[sol1-Python3]

class Solution:
    def minimumMoney(self, transactions: List[List[int]]) -> int:
        total_lose = mx = 0
        for cost, cashback in transactions:
            total_lose += max(cost - cashback, 0)
            mx = max(mx, min(cost, cashback))
        return total_lose + mx

[sol1-Java]

class Solution {
    public long minimumMoney(int[][] transactions) {
        var totalLose = 0L;
        var mx = 0;
        for (var t : transactions) {
            totalLose += Math.max(t[0] - t[1], 0);
            mx = Math.max(mx, Math.min(t[0], t[1]));
        }
        return totalLose + mx;
    }
}

[sol1-C++]

class Solution {
public:
    long long minimumMoney(vector<vector<int>> &transactions) {
        long total_lose = 0L;
        int mx = 0;
        for (auto &t : transactions) {
            total_lose += max(t[0] - t[1], 0);
            mx = max(mx, min(t[0], t[1]));
        }
        return total_lose + mx;
    }
};

[sol1-Go]

func minimumMoney(transactions [][]int) int64 {
	totalLose, mx := 0, 0
	for _, t := range transactions {
		totalLose += max(t[0]-t[1], 0)
		mx = max(mx, min(t[0], t[1]))
	}
	return int64(totalLose + mx)
}

func min(a, b int) int { if b < a { return b }; return a }
func max(a, b int) int { if b > a { return b }; return a }

复杂度分析

• 时间复杂度：O(n)，其中 n 为 transactions 的长度。
• 空间复杂度：O(1)，仅用到若干变量。

思考题

如果把题干的「任意一种」改成「至少一种」要怎么做？

可以参考 1665. 完成所有任务的最少初始能量 。