题目分析

本题是第87场双周赛的最后一题，有一定的难度，但是想一下也是可以想出来的。小伙伴们不要害怕，先试一下吧。

贪心

我们发现如果某个东西的cashback大于等于cost，说明这个东西是不会出现在前面的。

这是本题最重要的一句话，假设买的最后一个东西是m，那么如果n的cashback小于cost，那么所花的钱一定大于不买n所花的钱。

不妨设不买n花的钱是A，直接买m，需要的钱总数为A + cost[m]。
那么买了n后，花的钱是A + cost[n] - cashback[n]，然后再买m，需要的钱总数为A + cost[n] - cashback[n] + cost[m]，一定是大于A + cost[m]。

为了使任何顺序钱都够用，因此要计算出最花钱的钱总数。所以要将所有cashback小于cost的商品都选择，计算出所花的钱sum。

然后要选择某个商品进行最后的购买(此时不能计算收益cashback)，直接遍历数组即可，如果选择了cashback小于cost的商品进行最后的购买，则需要加上该商品对应的收益cashback，因为计算sum的时候已经计算过了，如果选择了cashback大于等于cost的商品进行最后的购买，则需要加上该商品对应的花费cost。

算法的**时间复杂度为O(n)，空间复杂度为O(1)**。

class Solution {
    public long minimumMoney(int[][] transactions) {
        long sum = 0;
        for (int[] p : transactions) {
            if (p[0] > p[1]) {
                sum += p[0] - p[1];
            }
        }
        long res = 0;
        for (int[] p : transactions) {
            res = Math.max(res, sum + Math.min(p[0], p[1]));
        }
        return res;
    }
}

刷题总结

贪心题目一般代码量都不会很大，比赛的时候也不需要去严格证明猜想的正确性，凭借感觉来就好，如果解答不正确，可以看一下样例，然后进行修正。如果思路不对再换其他方案。贪心的题目一次性就想出正确的结果也比较困难。