貪心算法：

• 特點：

  • 從局部最優(yōu)，從而達到全局最優(yōu)
  • 將一個問題進行分解為子問題，由子問題最佳得到全局最佳【關(guān)鍵在于怎么分解】；
  • 分解：
    • 橫向分解：分解為不同的情況，分別進行考慮，最優(yōu)情況往往取決于部分情況；
    • 縱向分解：分為不同的步驟，保證當(dāng)前步驟的最優(yōu)情況；

• 經(jīng)典題型：

  • 簡單題型：

    • 分發(fā)餅干，檸檬睡找零類似，確定一個最優(yōu)解的方向；
    • 分發(fā)糖果【兩個維度】：將相對關(guān)系分解為：左相關(guān) && 右相關(guān)，同時成立；
    • 數(shù)組經(jīng)過k次反轉(zhuǎn)：分解負數(shù) 0 正數(shù)，最后對k和最小值進行操作；

  • 中等題型：

    • 序列問題：

      • 擺動序列：分解為三個過程，平上，平下，平平；
      • 單調(diào)遞增的數(shù)字：對數(shù)字，存在兩個方向的遍歷，同時還得歸納總結(jié)出推導(dǎo)公式；

    • 股票問題：最優(yōu)是動態(tài)規(guī)劃，局部最優(yōu)：收集每天的正利潤，全局最優(yōu)：求得最大利潤。

    • 兩個維度問題：確定一個維度，判斷另一個【局部和全局】；

      • 身高重建隊列

    • 區(qū)間問題：區(qū)間=》范圍問題【屬于兩個維度問題】；

      • 跳躍游戲I：范圍問題；

      • 跳躍游戲II：在過程上有約束；

      • 弓箭引爆氣球：求區(qū)間之間的交集【使用min】；

      • 劃分字母區(qū)間：將字符映射為區(qū)間，統(tǒng)計每個字符最后出現(xiàn)的位置，然后就可以得到區(qū)間，然后跳躍游戲II的邏輯思路，統(tǒng)計已經(jīng)遍歷過的最大位置和當(dāng)前位置的關(guān)系；

        基本：先聚類為區(qū)間問題，然后區(qū)間求并，求差集

  • 有點難度：

    • 加油站：對于出發(fā)點的判斷【更偏向模擬題】
    • 監(jiān)控二叉樹：極端條件的判斷【優(yōu)先葉子節(jié)點的父節(jié)點】