6187. 完成所有交易的初始最少钱数(每日一难phase2--day19)

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

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

解析：

• 任意顺序，都能交易成功，说明需要找最差交易情况所需要的钱；
• 因此，需要先买赔钱的，最差钱一定在赔钱中产生，需要把赔钱的买完，买赔钱的会让花费更多，然后再买一个赚钱的花费最大的；
• 需要考虑第一个情况：赔钱中哪个最后一个买，肯定是cashbacki最大的最后一个买，这样需要的钱更多；
• 还需要考虑的就是赚钱中需要买一个，买哪个？肯定是买需要花费最大的。
• 另外需要考虑的的情况是，想买赚钱的最后一个，就需要把最后一个赔钱的给卖出去，这是就要判断到底是买赚钱的第一个，还是不卖赔钱的最后一个需要花费的大？
• 例如 ： [[7,2],[0,10],[5,0],[4,1],[5,8],[5,9]]
• 最后需要买[7,2], 需要比较买完7，不卖2产生一个的花费 和 买完7，卖了2，再买5的花费；也就是比较赔钱的最后一个卖出价格，和赚钱的第一个买入价格大小。买入大肯定选买入，卖出大肯定不卖出需要的钱是最大。

代码：

class Solution {
    typedef long long ll;
public:
    long long minimumMoney(vector<vector<int>>& transactions) {
        int n=transactions.size();
        ll res=0,cur=0;
        int mx=0;
        for(auto a :transactions){
        	// 赔钱中记录最后一个最大卖出钱数
        	// 并用res记录每次交易之后的钱数
            if(a[0]>=a[1])
                res+=a[0]-a[1],mx=max(mx,a[1]);
            // 赚钱中记录买入的最大值
            else 
                cur=cur>a[0]?cur:a[0];
        }
        // cur大就要卖出mx（res已经包含），买入cur；
        // mx大就说明不需要卖出mx，将mx加回来
        return cur>mx?res+cur:res+mx;
    }
};