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

代码随想录：原文

力扣题目：1005.K次取反后最大化的数组和

1.1 思路

两步贪心：

• 局部最优：让绝对值大的负数变为正数，当前数值达到最大
• 整体最优：整个数组和达到最大
• 局部最优：只找数值最小的正整数进行反转，当前数值和可以达到最大
• 全局最优：整个 数组和 达到最大。

1.2 代码实现

class Solution {
static bool cmp(int a, int b) {
    return abs(a) > abs(b);
}
public:
    int largestSumAfterKNegations(vector<int>& A, int K) {
        sort(A.begin(), A.end(), cmp);       // 第一步
        for (int i = 0; i < A.size(); i++) { // 第二步
            if (A[i] < 0 && K > 0) {
                A[i] *= -1;
                K--;
            }
        }
        if (K % 2 == 1) A[A.size() - 1] *= -1; // 第三步
        int result = 0;
        for (int a : A) result += a;        // 第四步
        return result;
    }
};

• 时间复杂度: $O(nlogn)$
• 空间复杂度: $O(1)$

2. 加油站

代码随想录：原文

力扣题目：1005.K次取反后最大化的数组和

2.1 思路

暴力方法

• 遍历每一个加油站为起点的情况，模拟一圈
• for循环适合模拟从头到尾的遍历，而while循环适合模拟环形遍历，要善于使用while
• 时间复杂度：$O(n^2)$

贪心算法

• 情况一：如果gas的总和小于cost总和，那么无论从哪里出发，一定是跑不了一圈的
• 情况二：rest[i] = gas[i]-cost[i]为一天剩下的油，i从0开始计算累加到最后一站，如果累加没有出现负数，说明从0出发，油就没有断过，那么0就是起点。
• 情况三：如果累加的最小值是负数，汽车就要从非0节点出发，从后向前，看哪个节点能把这个负数填平，能把这个负数填平的节点就是出发节点。

2.2 代码实现

class Solution {
public:
    int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {
        int curSum = 0;
        int min = INT_MAX; // 从起点出发，油箱里的油量最小值
        for (int i = 0; i < gas.size(); i++) {
            int rest = gas[i] - cost[i];
            curSum += rest;
            if (curSum < min) {
                min = curSum;
            }
        }
        if (curSum < 0) return -1;  // 情况1
        if (min >= 0) return 0;     // 情况2
                                    // 情况3
        for (int i = gas.size() - 1; i >= 0; i--) {
            int rest = gas[i] - cost[i];
            min += rest;
            if (min >= 0) {
                return i;
            }
        }
        return -1;
    }
};

3. 分发糖果

代码随想录：原文

力扣题目：135. 分发糖果

3.1 思路

• 两边一起考虑一定会顾此失彼
  先确定右边评分大于左边的情况（也就是从前向后遍历）
• 局部最优：只要右边评分比左边大，右边的孩子就多一个糖果
• 全局最优：相邻的孩子中，评分高的右孩子获得比左边孩子更多的糖果

// 从前向后
for (int i = 1; i < ratings.size(); i++) {
    if (ratings[i] > ratings[i - 1]) candyVec[i] = candyVec[i - 1] + 1;
}

再确定左孩子大于右孩子的情况（从后向前遍历）

• 局部最优：取candyVec[i + 1] + 1 和 candyVec[i] 最大的糖果数量，保证第i个小孩的糖果数量既大于左边的也大于右边的
• 全局最优：相邻的孩子中，评分高的孩子获得更多的糖果
• 取candyVec[i + 1] + 1 和 candyVec[i] 最大的糖果数量，candyVec[i]只有取最大的才能既保持对左边candyVec[i - 1]的糖果多，也比右边candyVec[i + 1]的糖果多

// 从后向前
for (int i = ratings.size() - 2; i >= 0; i--) {
    if (ratings[i] > ratings[i + 1] ) {
        candyVec[i] = max(candyVec[i], candyVec[i + 1] + 1);
    }
}

3.2 代码实现

class Solution {
public:
    int candy(vector<int>& ratings) {
        vector<int> candyVec(ratings.size(), 1);
        // 从前向后
        for (int i = 1; i < ratings.size(); i++) {
            if (ratings[i] > ratings[i - 1]) candyVec[i] = candyVec[i - 1] + 1;
        }
        // 从后向前
        for (int i = ratings.size() - 2; i >= 0; i--) {
            if (ratings[i] > ratings[i + 1] ) {
                candyVec[i] = max(candyVec[i], candyVec[i + 1] + 1);
            }
        }
        // 统计结果
        int result = 0;
        for (int i = 0; i < candyVec.size(); i++) result += candyVec[i];
        return result;
    }
};

4. 总结

• 坚持用贪心的思考方式（局部最优，全局最优）
• 不好两头兼顾的题目，处理好一边再处理另一边