今日內(nèi)容

• 貪心理論基礎(chǔ)
• Leetcode. 455 分發(fā)餅干
• Leetcode. 376 擺動(dòng)序列
• Leetcode. 53 最大子序和

貪心理論基礎(chǔ)

貪心算法的本質(zhì)就是選擇每一階段的最優(yōu)，達(dá)到全局上的最優(yōu)。

貪心算法和之前學(xué)到的所有方法相比，它沒有固定的使用套路，也沒有固定的驗(yàn)證法來確認(rèn)本題是否適用貪心算法。

對(duì)于何時(shí)應(yīng)該使用貪心，那就只能手動(dòng)模擬推導(dǎo)一下。如果模擬推導(dǎo)感覺可以根據(jù)局部最優(yōu)推出全局最優(yōu)，并且也找不出反例的話，就用貪心吧。

Leetcode. 455 分發(fā)餅干

文章鏈接：代碼隨想錄 (programmercarl.com)

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

本題的局部最優(yōu)就是拿目前最大的餅干來滿足胃口最大的孩子，從而達(dá)到全局最優(yōu)：盡可能多的孩子被喂飽。而且似乎也找不出反例，那么就可以使用貪心算法解決。

因此，可以寫出如下代碼：

class Solution {// 從大到小進(jìn)行貪心public int findContentChildren(int[] g, int[] s) {Arrays.sort(g);Arrays.sort(s);int index = s.length - 1;int result = 0;for (int i = g.length - 1; i >= 0; i--){ // 注意這里遍歷的是 胃口if (index >= 0 && s[index] >= g[i]){index--;result++;}}return result;}
}

• 時(shí)間復(fù)雜度：O(nlogn)
• 空間復(fù)雜度：O(1)

注意代碼中，for 循環(huán)是在表示小孩胃口的數(shù)組中進(jìn)行遍歷的，這樣是必須的。因?yàn)榧偃鐚?duì)餅干尺寸數(shù)組進(jìn)行遍歷，則可能遇到如下圖所示情況：

即 餅干尺寸數(shù)組遍歷完也找不到一個(gè)匹配當(dāng)前孩子胃口的結(jié)果，進(jìn)而影響結(jié)果。如果我們的貪心思想是先用尺寸小的餅干滿足小胃口的孩子優(yōu)先的話，此時(shí)遍歷餅干尺寸數(shù)組是正確的。

Leetcode. 376 擺動(dòng)序列

文章鏈接：代碼隨想錄 (programmercarl.com)

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

本題的局部思想就是獲取單調(diào)坡上的兩端節(jié)點(diǎn)，不理會(huì)單調(diào)坡中間的節(jié)點(diǎn)，獲取兩個(gè)局部峰值。使整個(gè)序列的局部峰值最多，就可以獲得全局最優(yōu)：得到最長(zhǎng)擺動(dòng)序列。

要想知道當(dāng)前節(jié)點(diǎn)是否為單調(diào)坡的兩端，就需要知曉該節(jié)點(diǎn)的前坡值 pre 和 后坡值 next。其中 pre = nums[i] - nums[i - 1]，next = nums[i + 1] - nums[i]。當(dāng) pre > 0, next < 0 或?pre <?0, next >?0時(shí)就說明當(dāng)前節(jié)點(diǎn)是坡的兩端。

知曉了兩端的判斷方式，就需要列出單調(diào)坡中可能出現(xiàn)的情況：

1. 上下坡中有平坡。如圖所示，此時(shí)要么去除前三個(gè)重復(fù)元素，要么去除后三個(gè)重復(fù)元素。所以考慮這種情況后，上面的條件就變?yōu)榱?當(dāng) pre >= 0, next < 0 或?pre <= 0, next >?0 時(shí)就說明當(dāng)前節(jié)點(diǎn)是坡的兩端。
2. 數(shù)組首位兩端。假如整個(gè)數(shù)組只有兩個(gè)元素，根據(jù)上述的前后坡值是無法計(jì)算出來的，因?yàn)檫@樣需要三個(gè)元素得出。因此可以假設(shè)最左邊的元素前有個(gè)平坡，然后最右邊的元素自動(dòng)視作是一個(gè)峰值。

根據(jù)上述兩種情況可以寫出如下代碼：

// 版本一
class Solution {
public:int wiggleMaxLength(vector<int>& nums) {if (nums.size() <= 1) return nums.size();int curDiff = 0; // 當(dāng)前一對(duì)差值int preDiff = 0; // 前一對(duì)差值int result = 1;  // 記錄峰值個(gè)數(shù)，序列默認(rèn)序列最右邊有一個(gè)峰值for (int i = 0; i < nums.size() - 1; i++) {curDiff = nums[i + 1] - nums[i];// 出現(xiàn)峰值if ((preDiff <= 0 && curDiff > 0) || (preDiff >= 0 && curDiff < 0)) {result++;}preDiff = curDiff;}return result;}
};

但這個(gè)代碼依然完成不了，原因就在于 preDiff = curDiff 這一行。

實(shí)際上，除了上述兩個(gè)情況以外還有一個(gè)情況：單調(diào)坡上有個(gè)平坡。

面對(duì)這種情況，如果根據(jù) 版本一 的代碼所示，遍歷每個(gè)元素時(shí)都更新一次前坡值，那么它會(huì)把第三個(gè) 2 認(rèn)為是一次擺動(dòng)，但實(shí)際上這只是單調(diào)坡上的平坡的一個(gè)轉(zhuǎn)折點(diǎn)，并沒有擺動(dòng)。

要想解決該情況，則需要在擺動(dòng)真正發(fā)生時(shí)更新前坡值。因此，改良后的代碼如下：

class Solution {public int wiggleMaxLength(int[] nums) {int pre = 0;int cur = 0;int result = 1; // 默認(rèn)最右邊的元素算一個(gè)擺動(dòng)序列for (int i = 0; i < nums.length - 1; i++){ // 注意條件表達(dá)式已經(jīng)將最后一個(gè)元素排除cur = nums[i + 1] - nums[i];if (pre >= 0 && cur < 0 || pre <= 0 && cur > 0){result++;pre = cur; // 擺動(dòng)發(fā)生時(shí)才更新前坡值}}return result;}
}

• 時(shí)間復(fù)雜度：O(n)
• 空間復(fù)雜度：O(1)

Leetcode. 53 最大子序和

文章鏈接：代碼隨想錄 (programmercarl.com)

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

本題的局部最優(yōu)就是當(dāng)前元素若加入進(jìn)來后導(dǎo)致總和為負(fù)數(shù)后，則重新求和。因?yàn)楸绢}要求最大的連續(xù)子序，所以當(dāng)總和為負(fù)數(shù)后，總是會(huì)拉低得到的結(jié)果，因此碰到使總和為負(fù)數(shù)的元素時(shí)就重置總和。

本題思路如下圖所示：

寫出如下代碼：

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){ // 記錄當(dāng)前最大總和result = count;}if (count < 0){count = 0;} // 當(dāng)總和為負(fù)數(shù)時(shí)，重置}return result;}
}

• 時(shí)間復(fù)雜度：O(n)
• 空間復(fù)雜度：O(1)

總結(jié)

貪心算法真是給了個(gè)下馬威，一下子難以徹底消化貪心算法的使用。

目前看來，貪心算法最重要的還是找到題目中什么是局部最優(yōu)，這樣才好進(jìn)行下一步。