摘要

• 贪心法的思考一般都贴合常识，比较直观，但是要写出逻辑正确的代码并不简单。
• 如何将全局最优分解为几步容易求解的局部最优并最终“合成”全局最优，是一个思考的方向。

LeetCode1005 K次取反后最大化的数组和

1005. K 次取反后最大化的数组和 - 力扣（Leetcode）

• 贪心法一般都贴合常识，比较直观，要取反后让数组和最大，首先要考虑每一步如何取反能让数组和增大：
  • 对一个负数取反，数组和肯定会增大，对绝对值越大的负数取反，数组和越大。
  • 对0取反，数组和不变
  • 对一个正数取反，数组和会变小，如果一定要对正数取反，应该绝对值小的正数取反
• 以上每种情况都和绝对值有关，所以首先想到将数组按绝对值从大到小排列，然后从左向右遍历一次数组：
  • 遇到一个负数，则取反，然后k--
  • 遇到0或正数不进行操作
  • 遍历的同时计算数组的和
• 遍历完一次数组后，如果k > 0，则不断对数组最后一个元素（即绝对值最小的元素）取反直到k == 0。

完整的题解代码如下

class Solution {
public:
    static bool cmp(int a, int b) {
        return abs(a) > abs(b);
    }
    int largestSumAfterKNegations(vector<int>& nums, int k) {
        sort(nums.begin(), nums.end(), cmp);
        
        int sum = 0;
        for (int i = 0; i < nums.size(); i++) {
            if (nums[i] < 0 && k > 0) {
                nums[i] *= -1;
                k--;
            }
            sum += nums[i];
        }
        
        while (k) {
            nums[nums.size()- 1] *= -1;
            sum += 2 * nums[nums.size()- 1];
            k--;
        }
        return sum;
    }
};

LeetCode134 加油站

134. 加油站 - 力扣（Leetcode）

• 这道题的思路和跳跃游戏 (55. 跳跃游戏 - 力扣（Leetcode）) 以及跳跃游戏II(45. 跳跃游戏 II - 力扣（Leetcode）) 有一个相似的地方：就是在遍历数组的过程中，保存下一步决策需要的信息。
• 从左到右遍历一次gas和cost，计算gas[i] - cost[i]

• 从左到右遍历数组，首先假设以i为起点，

  • 计算汽车从i号加油站出发到i+1号加油站后剩余的燃油curGas。
  • 如果汽车剩余燃油值curGas小于0，说明从i不是一个合理的起点，假设i+1为起点，将curGas归零，继续计算每段行程后的curGas。
  • 另外，计算汽车行驶完整个环形路径后的剩余燃油totalGas，作为判断最后的起点坐标是否合理的依据。如果totalGas小于0，说明无论从哪里开始，都不能走完整个环形路径，因为汽车一开始的燃油量是0，并没有额外的燃油。

完整的题解代码如下

class Solution {
public:
    int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {
        int start = 0;
        int totalGas = 0;
        int curGas = 0;
        for (int i = 0; i < gas.size(); i++) {
            totalGas += gas[i] - cost[i];
            curGas += gas[i] - cost[i];
            if (curGas < 0) {
                curGas = 0;
                start = i + 1;
            }
        }
        return totalGas >= 0 ? start : -1;
    }
};

• 直观地来理解：totalGas的值告诉我们是否有解，即是否存在一个加油站作为起点使得汽车能走完环形路径；而curGas的值告诉我们start是否是一个合理的起点，如果start不是一个合理的起点，那么从start出发后经过的加油站组成的也不是一个合理的路径。所以我们直接认为从start 到i号的加油站都不是合理的起点，继续假设i+1是一个合理的起点。

LeetCode135 分发糖果

135. 分发糖果 - 力扣（Leetcode）

• 初见题目的想法：先从左到右遍历一次ratings数组，保证在两个相邻的孩子中，如果左边的孩子的ratings较大，那么他得到的糖果就会比右边的孩子多。再从右到左遍历一次ratings数组，保证在两个相邻的孩子中，如果右边的孩子的ratings较大，那么他得到的糖果就会比左边的孩子多。

初见题目的代码，思路还不够清晰，最后一个用例超时了。

class Solution {
public:
    int candy(vector<int>& ratings) {
        int res = ratings.size();
        vector<int> candies(res, 1);
        for (int i = 1; i < ratings.size(); i++) {
            if (ratings[i - 1] == ratings[i]) continue;
            else if (ratings[i - 1] > ratings[i]) {
                while (candies[i - 1] <= candies[i]) {
                    candies[i - 1]++;
                    res++;
                }
            }
            else {
                while (candies[i - 1] >= candies[i]) {
                    candies[i]++;
                    res++;
                }
            }
        }
        for (int i = ratings.size() - 1; i > 0; i--) {
            if (ratings[i - 1] == ratings[i]) continue;
            else if (ratings[i - 1] > ratings[i]) {
                while (candies[i - 1] <= candies[i]) {
                    candies[i - 1]++;
                    res++;
                }
            }
            else {
                while (candies[i - 1] >= candies[i]) {
                    candies[i]++;
                    res++;
                }
            }
        }
        return res;
    }
};

[图片上传失败...(image-b728c6-1683603409915)]

• 看过讲解后，这道题的贪心解法确实很巧妙，通过两步的局部最优得到了全局最优。
  • 相邻两个孩子评分更高的孩子会获得更多糖果，这描述了全局最优。
  • 当ratings[i - 1] < ratings[i]时，孩子i比孩子i-1得到的糖果更多。按照这个规则从左到右遍历一次ratings，如果两个孩子相邻且在右边的孩子（即孩子i）的ratings较大，则孩子i获得的糖果要比在左边的孩子（即孩子i-1）多。
    • 这保证了对于每个孩子i，如果在他的ratings比左边的孩子i-1大，则孩子i获得的糖果更多。这只保证了“每个孩子比左边评分较低的孩子获得的糖果更多”，是一步局部最优。
  • 同样的，当ratings[i] > ratings[i + 1]时，孩子i比孩子i+1得到的糖果更多。按照这个规则从右到左遍历一次ratings，如果两个孩子相邻且在左边的孩子（即孩子i）的ratings较大，则孩子i获得的糖果要比在右边的孩子（即孩子i+1）多。
    • 这保证了对于每个孩子i，如果在他的ratings比右边的孩子i+1大，则孩子i获得的糖果更多。这只保证了“每个孩子比右边评分较低的孩子获得的糖果更多”，是一步局部最优。
  • 对每个孩子，取以上两步中计算出的较大的糖果数，就能保证每个孩子既比左边评分较低的孩子获得的糖果更多，又比右边评分较低的孩子获得的糖果更多。
• 如何通过局部最优来得到全局最优？或许可以尝试思考把全局最优的规则分为局部最优的规则。这道题说难也难，说简单也简单，毕竟说白了就是先保证每个孩子比左边评分较低的孩子多，再保证每个孩子比右边评分较低的孩子多。将全局最优（相邻的孩子）分解为两个局部最优——比左边评分较低的多、比右边评分较低的多。如何把全局最优分解成容易实现的局部最优或许也是一个思考的方向。

题解代码如下

class Solution {
public:
    int candy(vector<int>& ratings) {
        vector<int> candies(ratings.size(), 1);

        for (int i = 1; i < ratings.size(); i++) {
            if (ratings[i - 1] < ratings[i]) 
                candies[i] = candies[i - 1] + 1;
        }

        for (int i = ratings.size() - 2; i >= 0; i--) {
            if (ratings[i] > ratings[i + 1]) 
                candies[i] = max(candies[i + 1] + 1, candies[i]);
        }

        int res = 0;
        for (auto& iter : candies) {
            res += iter;
        }
        return res;
    }
};