參考

理論

本質(zhì)：找到每個(gè)階段的局部最優(yōu)，然后去推導(dǎo)得到全局最優(yōu)
兩個(gè)極端：常識(shí)&&很難：

很多同學(xué)通過(guò)了貪心的題目，但都不知道自己用了貪心算法，因?yàn)樨澬挠袝r(shí)候就是常識(shí)性的推導(dǎo)，所以會(huì)認(rèn)為本應(yīng)該就這么做！

套路：
貪心沒(méi)有套路，說(shuō)白了就是常識(shí)性推導(dǎo)加上舉反例
做題的時(shí)候，只要想清楚 局部最優(yōu) 是什么，如果推導(dǎo)出全局最優(yōu)，其實(shí)就夠了。

貪心算法一般分為如下四步：

將問(wèn)題分解為若干個(gè)子問(wèn)題
找出適合的貪心策略
求解每一個(gè)子問(wèn)題的最優(yōu)解
將局部最優(yōu)解堆疊成全局最優(yōu)解
這個(gè)四步其實(shí)過(guò)于理論化了，我們平時(shí)在做貪心類的題目 很難去按照這四步去思考，真是有點(diǎn)“雞肋”。

Leetcode題目

簡(jiǎn)單題

455.分發(fā)餅干

思路：大餅干 喂 胃口大的kid，才能充分利用

class Solution {
    public int findContentChildren(int[] g, int[] s) {
        Arrays.sort(g);
        Arrays.sort(s);
        int j=s.length-1;
        int sum = 0;

        for(int i=g.length-1;i>=0;i--){
            if(j>=0 && s[j]>=g[i]){
                sum++;
                j--;
            }
        }
        return sum;
    }
}

中等題

序列問(wèn)題---376. 擺動(dòng)序列

思路：考慮情況

記錄擺動(dòng)條件：
prediff>0 && curdiff<0
或者 prediff<0 && curdiff>0

情況1：上下坡中有平坡

在圖中，當(dāng)i指向第一個(gè)2的時(shí)候，prediff > 0 && curdiff = 0 ，當(dāng) i 指向最后一個(gè)2的時(shí)候 prediff = 0 && curdiff < 0。
如果我們采用，刪左面三個(gè)2的規(guī)則，那么 當(dāng) prediff = 0 && curdiff < 0 也要記錄一個(gè)峰值。

綜合到上述：記錄條件【prediff>=0 && curdiff<0 或 prediff=<0 && curdiff>0】

情況2：首尾兩端

result初始為1（默認(rèn)最右面有一個(gè)峰值），
curDiff > 0 && preDiff <= 0，那么result++（計(jì)算了左面的峰值），最后得到的result就是2（峰值個(gè)數(shù)為2即擺動(dòng)序列長(zhǎng)度為2）

做法：初始化prediff=0

情況3：?jiǎn)握{(diào)有平坡

只需要在 這個(gè)坡度 擺動(dòng)變化的時(shí)候，更新prediff就行，這樣prediff在 單調(diào)區(qū)間有平坡的時(shí)候 就不會(huì)發(fā)生變化

做法：調(diào)整prediff更新位置

java實(shí)現(xiàn)

class Solution {
    public int wiggleMaxLength(int[] nums) {
    
        int prediff = 0;//考慮只有兩個(gè)元素的時(shí)候，默認(rèn)為0；為頭元素制造一個(gè)平坡
        int curdiff = 0;
        int result = 1;//默認(rèn)最右端有坡度
        //一個(gè)元素的時(shí)候
        if(nums.length == 0) return result;
        
        for(int i=0;i<nums.length-1;i++){//nums.length-1 因?yàn)樽钣叶艘呀?jīng)記錄了

            curdiff = nums[i+1] - nums[i];
             
            if((prediff>=0 && curdiff <0) || (prediff<=0 && curdiff >0)){
                result++;
                prediff = curdiff;
            }
        //prediff = curdiff;
        }
        return result;
    }
}

股票問(wèn)題---122. 買賣股票的最佳時(shí)機(jī) II

只有一只股票！當(dāng)前只有買股票或者賣股票的操作
關(guān)鍵點(diǎn)：想到其實(shí)最終利潤(rùn)是可以分解的：每天的利潤(rùn)
貪心：只收集每次的正利潤(rùn)

其實(shí)我們需要收集每天的正利潤(rùn)就可以，收集正利潤(rùn)的區(qū)間，就是股票買賣的區(qū)間，而我們只需要關(guān)注最終利潤(rùn)，不需要記錄區(qū)間。

java

class Solution {
    public int maxProfit(int[] prices) {
        int sum = 0;
        for(int i=0;i < prices.length-1;i++){
            if((prices[i+1] - prices[i])>= 0){
                sum += prices[i+1] - prices[i];
            }
        }

        return sum;
    }
}

兩個(gè)維度權(quán)衡問(wèn)題---135. 分發(fā)糖果

關(guān)鍵點(diǎn)：兩邊分別考慮
先確定 右邊比左邊高的情況；然后再確定 左邊比右邊高的情況文章來(lái)源地址http://www.zghlxwxcb.cn/news/detail-419231.html

class Solution {
    public int candy(int[] ratings) {
        int sum = 0;
        int len = ratings.length;
        int[] candy = new int[len];
        

        candy[0]=1;


        for(int i=1;i<len;i++){
            if(ratings[i] > ratings[i-1]){
                candy[i] = candy[i-1] +1;
            }else{
                candy[i] =1;
            }
        }

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

        for(int i=0;i<len;i++){
            sum += candy[i];
        }

        return sum;
    }
}

到了這里，關(guān)于貪心算法基礎(chǔ)及l(fā)eetcode例題的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！