摘要

• 貪心法的思考一般都貼合常識(shí)削葱，比較直觀，但是要寫出邏輯正確的代碼并不簡(jiǎn)單淳梦。
• 如何將全局最優(yōu)分解為幾步容易求解的局部最優(yōu)并最終“合成”全局最優(yōu)析砸，是一個(gè)思考的方向。

LeetCode1005 K次取反后最大化的數(shù)組和

1005. K 次取反后最大化的數(shù)組和 - 力扣（Leetcode）

• 貪心法一般都貼合常識(shí)爆袍，比較直觀首繁，要取反后讓數(shù)組和最大作郭，首先要考慮每一步如何取反能讓數(shù)組和增大：
  • 對(duì)一個(gè)負(fù)數(shù)取反，數(shù)組和肯定會(huì)增大弦疮，對(duì)絕對(duì)值越大的負(fù)數(shù)取反夹攒，數(shù)組和越大。
  • 對(duì)0取反胁塞，數(shù)組和不變
  • 對(duì)一個(gè)正數(shù)取反咏尝，數(shù)組和會(huì)變小，如果一定要對(duì)正數(shù)取反啸罢，應(yīng)該絕對(duì)值小的正數(shù)取反
• 以上每種情況都和絕對(duì)值有關(guān)编检，所以首先想到將數(shù)組按絕對(duì)值從大到小排列，然后從左向右遍歷一次數(shù)組：
  • 遇到一個(gè)負(fù)數(shù)伺糠，則取反蒙谓，然后k--
  • 遇到0或正數(shù)不進(jìn)行操作
  • 遍歷的同時(shí)計(jì)算數(shù)組的和
• 遍歷完一次數(shù)組后，如果k > 0训桶，則不斷對(duì)數(shù)組最后一個(gè)元素（即絕對(duì)值最小的元素）取反直到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）) 有一個(gè)相似的地方：就是在遍歷數(shù)組的過程中，保存下一步?jīng)Q策需要的信息舵揭。
• 從左到右遍歷一次gas和cost谤专，計(jì)算gas[i] - cost[i]

• 從左到右遍歷數(shù)組，首先假設(shè)以i為起點(diǎn)午绳，

  • 計(jì)算汽車從i號(hào)加油站出發(fā)到i+1號(hào)加油站后剩余的燃油curGas置侍。
  • 如果汽車剩余燃油值curGas小于0，說明從i不是一個(gè)合理的起點(diǎn)拦焚，假設(shè)i+1為起點(diǎn)蜡坊，將curGas歸零，繼續(xù)計(jì)算每段行程后的curGas赎败。
  • 另外秕衙，計(jì)算汽車行駛完整個(gè)環(huán)形路徑后的剩余燃油totalGas，作為判斷最后的起點(diǎn)坐標(biāo)是否合理的依據(jù)僵刮。如果totalGas小于0据忘，說明無論從哪里開始，都不能走完整個(gè)環(huán)形路徑搞糕，因?yàn)槠囈婚_始的燃油量是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的值告訴我們是否有解窍仰，即是否存在一個(gè)加油站作為起點(diǎn)使得汽車能走完環(huán)形路徑汉规；而curGas的值告訴我們start是否是一個(gè)合理的起點(diǎn)，如果start不是一個(gè)合理的起點(diǎn)驹吮，那么從start出發(fā)后經(jīng)過的加油站組成的也不是一個(gè)合理的路徑针史。所以我們直接認(rèn)為從start 到i號(hào)的加油站都不是合理的起點(diǎn)膏燕，繼續(xù)假設(shè)i+1是一個(gè)合理的起點(diǎn)。

LeetCode135 分發(fā)糖果

135. 分發(fā)糖果 - 力扣（Leetcode）

• 初見題目的想法：先從左到右遍歷一次ratings數(shù)組悟民，保證在兩個(gè)相鄰的孩子中，如果左邊的孩子的ratings較大篷就，那么他得到的糖果就會(huì)比右邊的孩子多射亏。再從右到左遍歷一次ratings數(shù)組，保證在兩個(gè)相鄰的孩子中竭业，如果右邊的孩子的ratings較大智润，那么他得到的糖果就會(huì)比左邊的孩子多。

初見題目的代碼未辆，思路還不夠清晰窟绷，最后一個(gè)用例超時(shí)了。

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)]

• 看過講解后咐柜，這道題的貪心解法確實(shí)很巧妙兼蜈，通過兩步的局部最優(yōu)得到了全局最優(yōu)。
  • 相鄰兩個(gè)孩子評(píng)分更高的孩子會(huì)獲得更多糖果拙友，這描述了全局最優(yōu)为狸。
  • 當(dāng)ratings[i - 1] < ratings[i]時(shí)，孩子i比孩子i-1得到的糖果更多遗契。按照這個(gè)規(guī)則從左到右遍歷一次ratings辐棒，如果兩個(gè)孩子相鄰且在右邊的孩子（即孩子i）的ratings較大，則孩子i獲得的糖果要比在左邊的孩子（即孩子i-1）多牍蜂。
    • 這保證了對(duì)于每個(gè)孩子i漾根，如果在他的ratings比左邊的孩子i-1大，則孩子i獲得的糖果更多鲫竞。這只保證了“每個(gè)孩子比左邊評(píng)分較低的孩子獲得的糖果更多”辐怕，是一步局部最優(yōu)。
  • 同樣的贡茅，當(dāng)ratings[i] > ratings[i + 1]時(shí)秘蛇，孩子i比孩子i+1得到的糖果更多。按照這個(gè)規(guī)則從右到左遍歷一次ratings顶考，如果兩個(gè)孩子相鄰且在左邊的孩子（即孩子i）的ratings較大赁还，則孩子i獲得的糖果要比在右邊的孩子（即孩子i+1）多。
    • 這保證了對(duì)于每個(gè)孩子i驹沿，如果在他的ratings比右邊的孩子i+1大艘策，則孩子i獲得的糖果更多。這只保證了“每個(gè)孩子比右邊評(píng)分較低的孩子獲得的糖果更多”渊季，是一步局部最優(yōu)朋蔫。
  • 對(duì)每個(gè)孩子罚渐，取以上兩步中計(jì)算出的較大的糖果數(shù)，就能保證每個(gè)孩子既比左邊評(píng)分較低的孩子獲得的糖果更多驯妄，又比右邊評(píng)分較低的孩子獲得的糖果更多荷并。
• 如何通過局部最優(yōu)來得到全局最優(yōu)？或許可以嘗試思考把全局最優(yōu)的規(guī)則分為局部最優(yōu)的規(guī)則青扔。這道題說難也難源织，說簡(jiǎn)單也簡(jiǎn)單，畢竟說白了就是先保證每個(gè)孩子比左邊評(píng)分較低的孩子多微猖，再保證每個(gè)孩子比右邊評(píng)分較低的孩子多谈息。將全局最優(yōu)（相鄰的孩子）分解為兩個(gè)局部最優(yōu)——比左邊評(píng)分較低的多、比右邊評(píng)分較低的多凛剥。如何把全局最優(yōu)分解成容易實(shí)現(xiàn)的局部最優(yōu)或許也是一個(gè)思考的方向侠仇。

題解代碼如下

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;
    }
};