LeetCode：2412. 完成所有交易的初始最少钱数（贪心 java）

目录

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

题目描述：

实现代码与解析：

贪心

贪心：

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

实现代码与解析：

贪心

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

贪心：

        考虑最坏情况即可，就是在所有亏损进行的情况下，买一个花费最贵的。

        cur表示亏损总和。

        核心是最后一笔交易，如果是亏钱后的第一笔赚钱交易，那么直接买最贵的即可（赚的也多，后面的一定买得起）。如果是亏钱是最后一笔交易，那么实际上最后的这笔亏钱获得的收益我们没有利用到（后面没有能买的了），但是这笔交易cur中已经多减了，我们再给加上。

        所以：ma = Math.max(ma, Math.min(t[0], t[1]));