代碼隨想錄刷題day27丨455.分發(fā)餅干 ,376. 擺動(dòng)序列 ,53. 最大子序和

1.貪心算法理論基礎(chǔ)

• 貪心的本質(zhì)是選擇每一階段的局部最優(yōu)，從而達(dá)到全局最優(yōu)。

• 這么說有點(diǎn)抽象，來舉一個(gè)例子：

  例如，有一堆鈔票，你可以拿走十張，如果想達(dá)到最大的金額，你要怎么拿？

  指定每次拿最大的，最終結(jié)果就是拿走最大數(shù)額的錢。

  每次拿最大的就是局部最優(yōu)，最后拿走最大數(shù)額的錢就是推出全局最優(yōu)。

• 再舉一個(gè)例子如果是 有一堆盒子，你有一個(gè)背包體積為n，如何把背包盡可能裝滿，如果還每次選最大的盒子，就不行了。這時(shí)候就需要?jiǎng)討B(tài)規(guī)劃。

• 貪心算法并沒有固定的套路。難點(diǎn)就是如何通過局部最優(yōu)，推出整體最優(yōu)。

• 靠自己手動(dòng)模擬，如果模擬可行，就可以試一試貪心策略，如果不可行，可能需要?jiǎng)討B(tài)規(guī)劃。

• 如何驗(yàn)證可不可以用貪心算法呢？

  • 最好用的策略就是舉反例，如果想不到反例，那么就試一試貪心吧。

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

  • 將問題分解為若干個(gè)子問題
  • 找出適合的貪心策略
  • 求解每一個(gè)子問題的最優(yōu)解
  • 將局部最優(yōu)解堆疊成全局最優(yōu)解

2.題目

2.1分發(fā)餅干

• 題目鏈接：455. 分發(fā)餅干 - 力扣（LeetCode）

  

• 視頻講解：貪心算法，你想先喂哪個(gè)小孩？| LeetCode：455.分發(fā)餅干_嗶哩嗶哩_bilibili

• 文檔講解：https://programmercarl.com/0455.%E5%88%86%E5%8F%91%E9%A5%BC%E5%B9%B2.html

• 解題思路：貪心

  • 為了滿足更多的小孩，就不要造成餅干尺寸的浪費(fèi)。

    大尺寸的餅干既可以滿足胃口大的孩子也可以滿足胃口小的孩子，那么就應(yīng)該優(yōu)先滿足胃口大的。

  • 這里的局部最優(yōu)就是大餅干喂給胃口大的，充分利用餅干尺寸喂飽一個(gè)，全局最優(yōu)就是喂飽盡可能多的小孩。

    

• 代碼：

  class Solution {public int findContentChildren(int[] g, int[] s) {Arrays.sort(g);Arrays.sort(s);int result = 0;int index = s.length -1;for(int i = g.length - 1;i >= 0;i--){if(index >= 0 && s[index] >= g[i]){result++;index--;}}return result;}
  }
  

• 總結(jié)：

  • 小餅干先喂飽小胃口也可以

2.2擺動(dòng)序列

• 題目鏈接：376. 擺動(dòng)序列 - 力扣（LeetCode）

  

• 視頻講解：貪心算法，尋找擺動(dòng)有細(xì)節(jié)！| LeetCode：376.擺動(dòng)序列_嗶哩嗶哩_bilibili

• 文檔講解：https://programmercarl.com/0376.%E6%91%86%E5%8A%A8%E5%BA%8F%E5%88%97.html

• 解題思路：貪心

  • 

  • 局部最優(yōu)：刪除單調(diào)坡度上的節(jié)點(diǎn)（不包括單調(diào)坡度兩端的節(jié)點(diǎn)），那么這個(gè)坡度就可以有兩個(gè)局部峰值。

    整體最優(yōu)：整個(gè)序列有最多的局部峰值，從而達(dá)到最長擺動(dòng)序列。

  • 在計(jì)算是否有峰值的時(shí)候，大家知道遍歷的下標(biāo) i ，計(jì)算 prediff（nums[i] - nums[i-1]） 和 curdiff（nums[i+1] - nums[i]），如果prediff < 0 && curdiff > 0 或者 prediff > 0 && curdiff < 0 此時(shí)就有波動(dòng)就需要統(tǒng)計(jì)。

  • 本題要考慮三種情況：

    1. 情況一：上下坡中有平坡

       

    2. 情況二：數(shù)組首尾兩端

       • 針對序列[2,5]，可以假設(shè)為[2,2,5]，這樣它就有坡度了即 preDiff = 0，result 初始為 1（默認(rèn)最右面有一個(gè)峰值）

         

    3. 情況三：單調(diào)坡中有平坡

       

       • 我們應(yīng)該什么時(shí)候更新 prediff 呢？
         • 我們只需要在 這個(gè)坡度 擺動(dòng)變化的時(shí)候，更新 prediff 就行，這樣 prediff 在 單調(diào)區(qū)間有平坡的時(shí)候 就不會(huì)發(fā)生變化，造成我們的誤判。

• 代碼：

  class Solution {public int wiggleMaxLength(int[] nums) {if(nums.length <= 1){return nums.length;}//當(dāng)前差值int curDiff = 0;//上一個(gè)差值int preDiff = 0;//默認(rèn)最右邊有一個(gè)峰值int count = 1;//遍歷到倒數(shù)第二個(gè)就行，最右邊的已經(jīng)默認(rèn)了for(int i = 0;i < nums.length -1;i++){curDiff = nums[i + 1] - nums[i];if((curDiff > 0 && preDiff <= 0) || (curDiff < 0 && preDiff >= 0)){count++;preDiff = curDiff;}}return count;}
  }
  

• 總結(jié)：

  • 為什么 preDiff = curDiff 放在條件判斷內(nèi)部這個(gè)位置？
    • 為了保證只有在波動(dòng)方向改變時(shí)才更新 preDiff。如果波動(dòng)方向沒有變化（即不滿足 (curDiff > 0 && preDiff <= 0) || (curDiff < 0 && preDiff >= 0)），那么 preDiff 保持不變，等待下一次有效的波動(dòng)。

2.3最大子序和

• 題目鏈接：53. 最大子數(shù)組和 - 力扣（LeetCode）

  

• 視頻講解：貪心算法的巧妙需要慢慢體會(huì)！LeetCode：53. 最大子序和_嗶哩嗶哩_bilibili

• 文檔講解：https://programmercarl.com/0053.%E6%9C%80%E5%A4%A7%E5%AD%90%E5%BA%8F%E5%92%8C.html

• 解題思路：貪心

  • 局部最優(yōu)：當(dāng)前“連續(xù)和”為負(fù)數(shù)的時(shí)候立刻放棄，從下一個(gè)元素重新計(jì)算“連續(xù)和”，因?yàn)樨?fù)數(shù)加上下一個(gè)元素 “連續(xù)和”只會(huì)越來越小。
  • 全局最優(yōu)：選取最大“連續(xù)和”
  • 局部最優(yōu)的情況下，并記錄最大的“連續(xù)和”，可以推出全局最優(yōu)。

• 代碼：

  class Solution {public int maxSubArray(int[] nums) {int result = Integer.MIN_VALUE;int count = 0;for(int i = 0;i < nums.length;i++){count += nums[i];if(count > result){result = count;}if(count < 0){count = 0;}}return result;}
  }
  

• 總結(jié)：

  • 遇到連續(xù)和為負(fù)數(shù)才更新起始位置。并不是遇到負(fù)數(shù)就更新。