什么是貪心

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

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

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

1分發(fā)餅干

假設(shè)你是一位很棒的家長，想要給你的孩子們一些小餅干。但是，每個孩子最多只能給一塊餅干。

對每個孩子?i，都有一個胃口值?g[i]，這是能讓孩子們滿足胃口的餅干的最小尺寸；并且每塊餅干?j，都有一個尺寸?s[j]?。如果?s[j]?>= g[i]，我們可以將這個餅干?j?分配給孩子?i?，這個孩子會得到滿足。你的目標是盡可能滿足越多數(shù)量的孩子，并輸出這個最大數(shù)值。

示例?1:

輸入: g = [1,2,3], s = [1,1]
輸出: 1
解釋: 
你有三個孩子和兩塊小餅干，3個孩子的胃口值分別是：1,2,3。
雖然你有兩塊小餅干，由于他們的尺寸都是1，你只能讓胃口值是1的孩子滿足。
所以你應(yīng)該輸出1。

示例?2:

輸入: g = [1,2], s = [1,2,3]
輸出: 2
解釋: 
你有兩個孩子和三塊小餅干，2個孩子的胃口值分別是1,2。
你擁有的餅干數(shù)量和尺寸都足以讓所有孩子滿足。
所以你應(yīng)該輸出2.

提示：

• 1 <= g.length <= 3 * 104
• 0 <= s.length <= 3 * 104
• 1 <= g[i], s[j] <=?231 - 1

思路：

1. 排序: 首先，將孩子的胃口數(shù)組?g?和餅干的大小數(shù)組?s?分別按從小到大排序。這樣做是為了能夠從最小的胃口和最小的餅干開始匹配，以盡可能滿足更多的孩子。

2. 貪心策略: 使用貪心算法的核心思想，從胃口最大的孩子開始，嘗試給他們分配能滿足他們胃口的最小餅干。這里的貪心選擇是每次都選擇當前能夠滿足的最小餅干，以期望最終能夠滿足盡可能多的孩子。

3. 實現(xiàn)細節(jié):

   • 使用?index?表示當前可用的餅干數(shù)組的最后一個元素的下標。
   • 從最大胃口的孩子開始向最小胃口的孩子遍歷，嘗試找到合適的餅干分配。
   • 如果當前的餅干能夠滿足當前孩子的胃口，則結(jié)果?result?加一，并將?index?減一，表示使用了這個餅干。
   • 如果當前的餅干不能滿足當前孩子的胃口，則繼續(xù)向前嘗試下一個更大的餅干，直到找到合適的或者餅干用完。

4. 返回結(jié)果: 最終返回?result，即能夠滿足的孩子的數(shù)量。

代碼：

class Solution {
public:int findContentChildren(vector<int>& g, vector<int>& s) {// 將孩子數(shù)組和餅干數(shù)組按照從小到大排序sort(g.begin(), g.end()); // 按照孩子的胃口排序sort(s.begin(), s.end()); // 按照餅干的大小排序int index = s.size() - 1; // 餅干數(shù)組的下標int result = 0; // 結(jié)果，能滿足孩子的數(shù)量// 從胃口最大的孩子開始匹配餅干for (int i = g.size() - 1; i >= 0; i--) { // 遍歷胃口// 如果還有餅干可用且當前餅干滿足當前孩子的胃口if (index >= 0 && s[index] >= g[i]) { // 遍歷餅干result++; // 滿足一個孩子index--; // 使用了一個餅干，下標減一}}return result; // 返回滿足孩子的數(shù)量}
};

2擺動序列

如果連續(xù)數(shù)字之間的差嚴格地在正數(shù)和負數(shù)之間交替，則數(shù)字序列稱為?擺動序列 。第一個差（如果存在的話）可能是正數(shù)或負數(shù)。僅有一個元素或者含兩個不等元素的序列也視作擺動序列。

• 例如，?[1, 7, 4, 9, 2, 5]?是一個?擺動序列?，因為差值?(6, -3, 5, -7, 3)?是正負交替出現(xiàn)的。

• 相反，[1, 4, 7, 2, 5]?和?[1, 7, 4, 5, 5]?不是擺動序列，第一個序列是因為它的前兩個差值都是正數(shù)，第二個序列是因為它的最后一個差值為零。

子序列?可以通過從原始序列中刪除一些（也可以不刪除）元素來獲得，剩下的元素保持其原始順序。

給你一個整數(shù)數(shù)組?nums?，返回?nums?中作為?擺動序列?的?最長子序列的長度?。

示例 1：

輸入：nums = [1,7,4,9,2,5]
輸出：6
解釋：整個序列均為擺動序列，各元素之間的差值為 (6, -3, 5, -7, 3) 。

示例 2：

輸入：nums = [1,17,5,10,13,15,10,5,16,8]
輸出：7
解釋：這個序列包含幾個長度為 7 擺動序列。
其中一個是 [1, 17, 10, 13, 10, 16, 8] ，各元素之間的差值為 (16, -7, 3, -3, 6, -8) 。

示例 3：

輸入：nums = [1,2,3,4,5,6,7,8,9]
輸出：2

提示：

• 1 <= nums.length <= 1000
• 0 <= nums[i] <= 1000

思路：

代碼：

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

整體最優(yōu)：整個序列有最多的局部峰值，從而達到最長擺動序列。只需要統(tǒng)計數(shù)組的峰值數(shù)量就可以了。

1. 初始化：

   • curDiff?初始化為?0，表示當前一對相鄰元素的差值。
   • preDiff?也初始化為?0，表示前一對相鄰元素的差值。
   • result?初始化為?1，因為序列默認至少有一個峰值。

2. 處理邊界情況：

   • 如果數(shù)組?nums?的大小?<= 1，直接返回?nums.size()，因為這種情況下不可能形成長度大于1的擺動序列。

3. 遍歷數(shù)組：

   • 循環(huán)遍歷數(shù)組?nums，從第一個元素到倒數(shù)第二個元素 (i < nums.size() - 1)。

4. 計算差值：

   • 計算?curDiff?為?nums[i + 1] - nums[i]，即當前兩個相鄰元素的差值。

5. 檢測峰值和谷值：

   • 當?preDiff <= 0 && curDiff > 0?或者?preDiff >= 0 && curDiff < 0?時，表示出現(xiàn)了擺動的峰值或者谷值。
   • 在這些情況下，增加?result?的計數(shù)，因為它們是擺動序列的關(guān)鍵點。

6. 返回結(jié)果：

   • 最終返回?result，即最長擺動子序列的長度。

class Solution {
public:int wiggleMaxLength(vector<int>& nums) {if (nums.size() <= 1) return nums.size();int curDiff = 0; // 當前一對差值int preDiff = 0; // 前一對差值int result = 1;  // 記錄峰值個數(shù)，序列默認序列最右邊有一個峰值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; // 注意這里，只在擺動變化的時候更新prediff}}return result;}
};

3最大子數(shù)組和

給你一個整數(shù)數(shù)組?nums?，請你找出一個具有最大和的連續(xù)子數(shù)組（子數(shù)組最少包含一個元素），返回其最大和。

子數(shù)組

是數(shù)組中的一個連續(xù)部分。

示例 1：

輸入：nums = [-2,1,-3,4,-1,2,1,-5,4]
輸出：6
解釋：連續(xù)子數(shù)組?[4,-1,2,1] 的和最大，為?6 。

示例 2：

輸入：nums = [1]
輸出：1

示例 3：

輸入：nums = [5,4,-1,7,8]
輸出：23

提示：

• 1 <= nums.length <= 105
• -104 <= nums[i] <= 104

思路：

局部最優(yōu)：當前“連續(xù)和”為負數(shù)的時候立刻放棄，從下一個元素重新計算“連續(xù)和”，因為負數(shù)加上下一個元素 “連續(xù)和”只會越來越小。

全局最優(yōu)：選取最大“連續(xù)和”

局部最優(yōu)的情況下，并記錄最大的“連續(xù)和”，可以推出全局最優(yōu)。

該貪心算法實現(xiàn)的思路是在遍歷數(shù)組的過程中，持續(xù)累積子數(shù)組的元素和，同時不斷更新最大子數(shù)組之和。如果當前累積和變?yōu)樨摂?shù)，就重新開始計算子數(shù)組和，以期獲得更大的子數(shù)組和。

代碼：

class Solution {
public:int maxSubArray(vector<int>& nums) {int result = INT32_MIN; // 初始化最大和為負無窮int count = 0; // 當前累積和for (int i = 0; i < nums.size(); i++) {count += nums[i]; // 累加當前元素到當前和if (count > result) {result = count; // 更新最大和為當前和}if (count <= 0) {count = 0; // 如果當前和小于等于0，則重新開始計算累積和}}return result; // 返回最大和}
};