0.引言
● 理論基礎
● 455.分發(fā)餅干
● 376. 擺動序列
● 53. 最大子序和
0.理論基礎
貪心算法一般分為如下四步：
- 將問題分解為若干個子問題
- 找出適合的貪心策略
- 求解每一個子問題的最優(yōu)解
- 將局部最優(yōu)解堆疊成全局最優(yōu)解
這個四步其實過于理論化了，我們平時在做貪心類的題目 很難去按照這四步去思考，真是有點“雞肋”。
做題的時候，只要想清楚 局部最優(yōu) 是什么，如果推導出全局最優(yōu)，其實就夠了。
455.# 分發(fā)餅干
| Category | Difficulty | Likes | Dislikes |
|---|---|---|---|
| algorithms | Easy (56.72%) | 685 | - |
假設你是一位很棒的家長，想要給你的孩子們一些小餅干。但是，每個孩子最多只能給一塊餅干。
對每個孩子 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的孩子滿足。
所以你應該輸出1。
示例 2:
輸入: g = [1,2], s = [1,2,3]
輸出: 2
解釋:
你有兩個孩子和三塊小餅干，2個孩子的胃口值分別是1,2。
你擁有的餅干數(shù)量和尺寸都足以讓所有孩子滿足。
所以你應該輸出2.
提示：
1 <= g.length <= 3 * 10<sup>4</sup>0 <= s.length <= 3 * 10<sup>4</sup>1 <= g[i], s[j] <= 2<sup>31</sup> - 1
貪心思想
大尺寸的餅干既可以滿足胃口大的孩子也可以滿足胃口小的孩子，那么就應該優(yōu)先滿足胃口大的。
這里的局部最優(yōu)就是大餅干喂給胃口大的，充分利用餅干尺寸喂飽一個，全局最優(yōu)就是喂飽盡可能多的小孩。
先排序，再分發(fā)。
/*
* @lc app=leetcode.cn id=455 lang=cpp
*
* [455] 分發(fā)餅干
*/
// @lc code=start
class Solution {
public:
int findContentChildren(vector<int>& g, vector<int>& s) {
sort(g.begin(), g.end());
sort(s.begin(), s.end());
int child = 0; // child s下標
int candy = 0; // candy g下標
// 小餅干先喂飽小胃口
while (child < g.size() && candy < s.size()) {
if (s[candy] >= g[child]) { // 滿足當前孩子
child++;
}
candy++;
}
return child; // 孩子滿足的個數(shù)
}
};
// @lc code=end
376. # 擺動序列
| Category | Difficulty | Likes | Dislikes |
|---|---|---|---|
| algorithms | Medium (47.17%) | 912 | - |
如果連續(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
解題思路：
局部最優(yōu)：刪除單調(diào)坡度上的節(jié)點（不包括單調(diào)坡度兩端的節(jié)點），那么這個坡度就可以有兩個局部峰值。
整體最優(yōu)：整個序列有最多的局部峰值，從而達到最長擺動序列。
-局部最優(yōu)推出全局最優(yōu)，并舉不出反例，那么試試貪心！
實際操作上，其實連刪除的操作都不用做，因為題目要求的是最長擺動子序列的長度，所以只需要統(tǒng)計數(shù)組的峰值數(shù)量就可以了（相當于是刪除單一坡度上的節(jié)點，然后統(tǒng)計長度）
這就是貪心所貪的地方，讓峰值盡可能的保持峰值，然后刪除單一坡度上的節(jié)點
在計算是否有峰值的時候，大家知道遍歷的下標i ，計算prediff（nums[i] - nums[i-1]） 和 curdiff（nums[i+1] - nums[i]），如果prediff < 0 && curdiff > 0 或者 prediff > 0 && curdiff < 0 此時就有波動就需要統(tǒng)計。
這是我們思考本題的一個大題思路，但本題要考慮三種情況：
- 情況一：上下坡中有平坡
- 情況二：數(shù)組首尾兩端
- 情況三：單調(diào)坡中有平坡
/*
* @lc app=leetcode.cn id=376 lang=cpp
*
* [376] 擺動序列
*/
// @lc code=start
class Solution {
public:
int wiggleMaxLength(vector<int>& nums) {
if (nums.size() <= 1) return nums.size();
int cur_diff = 0; // 當前一對差值
int pre_diff = 0; // 前一對差值
int result = 1; // 記錄峰值個數(shù)，序列默認序列最右邊有一個峰值
for (int i = 0; i < nums.size() - 1; i++) {
cur_diff = nums[i + 1] - nums[i];
// 出現(xiàn)峰值
if ((pre_diff <= 0 && cur_diff > 0) || (pre_diff >= 0 && cur_diff < 0)) {
result++;
pre_diff = cur_diff; // 注意這里，只在擺動變化的時候更新prediff
}
}
return result;
}
};
// @lc code=end
其他參考：
在這個問題中，up 和 down 分別表示以當前元素為結(jié)尾的最長上升子序列和最長下降子序列的長度。這里的上升和下降子序列指的是擺動序列的一部分，即一個子序列中相鄰元素之間的差值嚴格正負交替。
- up：以當前元素結(jié)尾的最長上升子序列的長度。這意味著在這個子序列中，當前元素的值大于前一個元素，同時滿足擺動序列的性質(zhì)（差值嚴格正負交替）。
- down：以當前元素結(jié)尾的最長下降子序列的長度。這意味著在這個子序列中，當前元素的值小于前一個元素，同時滿足擺動序列的性質(zhì)（差值嚴格正負交替）。
在遍歷數(shù)組的過程中，我們比較相鄰的元素，根據(jù)它們的大小關系更新 up 和 down 的值。當當前元素大于前一個元素時，我們更新 up 的值為 down + 1，表示當前元素可以接在一個下降子序列的后面，形成一個更長的上升子序列。反之，如果當前元素小于前一個元素，我們更新 down 的值為 up + 1，表示當前元素可以接在一個上升子序列的后面，形成一個更長的下降子序列。如果當前元素等于前一個元素，我們不需要更新 up 和 down，因為它們不會對擺動序列產(chǎn)生影響。
/*
* @lc app=leetcode.cn id=376 lang=cpp
*
* [376] 擺動序列
*/
// @lc code=start
class Solution {
public:
int wiggleMaxLength(vector<int>& nums) {
int n = nums.size();
if (n < 2) return n; // 特判
// 有上坡才有下坡
int up = 1, down = 1; // 初始值都為1
for (int i = 1; i < n; i++) {
if (nums[i] > nums[i - 1]) {
up = down + 1;
} else if (nums[i] < nums[i - 1]) {
down = up + 1;
}
}
return max(up, down); // 返回較大值
}
};
// @lc code=end
53. # 最大子數(shù)組和
| Category | Difficulty | Likes | Dislikes |
|---|---|---|---|
| algorithms | Medium (54.85%) | 5970 | - |
給你一個整數(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 <= 10<sup>5</sup>-10<sup>4</sup> <= nums[i] <= 10<sup>4</sup>
進階：如果你已經(jīng)實現(xiàn)復雜度為 O(n) 的解法，嘗試使用更為精妙的 分治法 求解。
貪心
如果 -2 1 在一起，計算起點的時候，一定是從1開始計算，因為負數(shù)只會拉低總和，這就是貪心貪的地方！
局部最優(yōu)：當前“連續(xù)和”為負數(shù)的時候立刻放棄，從下一個元素重新計算“連續(xù)和”，因為負數(shù)加上下一個元素 “連續(xù)和”只會越來越小。
全局最優(yōu)：選取最大“連續(xù)和”
/*
* @lc app=leetcode.cn id=53 lang=cpp
*
* [53] 最大子數(shù)組和
*/
// @lc code=start
class Solution {
public:
int maxSubArray(vector<int>& nums) {
int max_sum = nums[0], cur_sum = nums[0];
for (int i = 1; i < nums.size(); ++i) {
// 如果 -2 1 在一起，計算起點的時候，一定是從1開始計算，
// 因為負數(shù)只會拉低總和，這就是貪心貪的地方！
cur_sum = max(cur_sum + nums[i], nums[i]);
max_sum = max(max_sum, cur_sum);
}
return max_sum;
}
};
// @lc code=end
