代码随想录算法训练营day27 | 贪心算法 | 455.分发饼干、376.摆动序列、53.最大子序和

文章目录

- 理论基础
- 解题步骤
- 455.分发饼干
- - 思路
  - 小结
- 376.摆动序列
- - 简单思路
  - 贪心思路
- 53.最大子序和
- - 思路

今天是贪心算法的第一天

理论基础

贪心的本质是选择每一阶段的局部最优，从而达到全局最优

在理论上，能使用贪心解决的问题有两个特点：具有最优子结构和贪心选择性，其中贪心选择性是贪心算法能使用的关键，只有最优子结构，可能用dp，可能用贪心，无法说明贪心适用。

贪心选择性：每一步贪心选出来的一定是原问题的最优解的一部分。
最优子结构：每一步贪心选完后会留下子问题，子问题的最优解和贪心选出来的解可以凑成原问题的最优解。

贪心的过程是只考虑当前的最优情况，然后遗留下一个规模变小了，但性质相同的子问题，如果贪心选出的是最优解，则本次贪心选出来的解一定是最终的最优解的一部分；剩下的子问题中的最优解与刚贪心选出来的解可以凑成原问题的最优解

实际上，贪心没有某类具体适用的题目，它是一种思想：局部最优之和为整体最优。在做题或面试时，手动模拟一下感觉可以局部最优推出整体最优，而且想不到反例，那么就试一试贪心。贪心有的时候就是常识性的推导，像1+1=2一样自然；有时需要数学推导，例如这道题目：链表：环找到了，那入口呢？ (opens new window)，这道题不用数学推导一下，就找不出环的起始位置，想试一下就不知道怎么试，这种题目确实需要数学简单推导一下

解题步骤

贪心算法一般分为如下四步：

将问题分解为若干个子问题
找出适合的贪心策略
求解每一个子问题的最优解
将局部最优解堆叠成全局最优解

这个四步其实过于理论化了，我们平时在做贪心类的题目很难去按照这四步去思考，真是有点“鸡肋”

做题的时候，只要想清楚局部最优是什么，如果推导出全局最优，其实就够了

贪心这一部分，实践比理论重要，直接上题目

455.分发饼干

题目链接：455. 分发饼干 - 力扣（LeetCode）

思路

大尺寸的饼干既可以满足胃口大的孩子也可以满足胃口小的孩子，那么就应该优先满足胃口大的

这里的局部最优就是大饼干喂给胃口大的，充分利用饼干尺寸喂饱一个，全局最优就是喂饱尽可能多的小孩

举个例子：

饼干9只有喂给胃口为7的小孩，这样才是整体最优解

我们可以先将饼干数组和小孩数组排序，然后从后向前遍历小孩数组，用大饼干优先满足胃口大的小孩，并统计满足的小孩数量

代码实现：

class Solution
{public:int findContentChildren(vector<int>& g, vector<int>& s){sort(s.begin(), s.end());sort(g,begin(), g.end());int index = s.size()-1;	// 饼干数组的下标int result = 0;// 从后向前遍历数组gfor(int i=g.size()-1; i>=0; --i){if(index >= 0 && s[index] >= g[i]){result++;index--;}}return result;}
};

时间复杂度：O(nlogn)
空间复杂度：O(1)

注意到代码中使用index来控制饼干数组的遍历，而不是使用for循环，因为一个饼干不能分配给多个小孩，每次外层遍历结束时，都要记录上次饼干数组遍历到的位置

另一个思路：小饼干喂饱小胃口，即先满足小胃口

代码实现：

class Solution {
public:int findContentChildren(vector<int>& g, vector<int>& s) {sort(g.begin(),g.end());sort(s.begin(),s.end());int index = 0;for(int i = 0; i < s.size(); i++) { // 饼干if(index < g.size() && g[index] <= s[i]){ // 胃口index++;}}return index;}
};

小结

这是贪心的一道入门题目。想清楚局部最优，想清楚全局最优，感觉局部最优是可以推出全局最优，并想不出反例，那么就试一试贪心

376.摆动序列

题目链接：376. 摆动序列 - 力扣（LeetCode）

简单思路

核心思想：最长摆动序列中相邻的两个数字对应着一次正负转换。原序列中连续的上升，对应着最长摆动序列中的一次上升，下降同理。

本题求最长摆动序列的长度，只需要求有多少次正负转换，正负转换的次数+1 就是最长摆动序列的长度。以示例二为例，如图：

376.摆动序列

这个序列的最长摆动序列为[1, 17, 5, 15, 5, 16, 8]，长度为7，每两个数字之间都对应着一次正负转换，对于连续的上升，如5->10->13->15，我们将其看做一次上升，这对应着最长摆动序列中5->15的上升

代码实现

class Solution {
public:int wiggleMaxLength(vector<int>& nums) {int count = 1;int gap = 0;for(int i=1; i<nums.size(); ++i){int cur = nums[i] - nums[i-1];if(cur != 0 && cur*gap <= 0)    // 如果异号，说明已经出现了正负翻转{gap = cur;count++;}}return count;}
};

贪心思路

核心思想：要使摆动序列尽量长，需要使摆动序列中相邻的两个数字之间相差最大

局部最优：删除单调坡度上的节点（不包括单调坡度两端的节点），那么这个坡度就可以有两个局部峰值或峰谷。

整体最优：整个序列有最多的局部峰值和峰谷，从而达到最长摆动序列

以示例二为例，如图：

376.摆动序列

最终，局部峰值和峰谷组成的序列即为最长摆动序列

相对于简单思路，这个思路可以获得最长摆动序列，不仅仅是它的长度

整体思路：我们用preDiff记录上一个峰值或峰谷的差值nums[prev + 1] - nums[prev]，curDiff记录当前差值nums[cur + 1] - nums[cur]，就像在函数中寻找极大值和极小值一样，如果preDiff < 0 && curDiff > 0，则当前的值nums[cur]就是极大值；如果preDiff > 0 && curDiff <= 0，则当前的值nums[cur]就是极小值，这些峰值和峰谷组合在一起，即可构成最长摆动序列

本题需要考虑异常情况：考虑平坡。平坡分成三种：上下中间有平坡，单调有平坡，数组首尾两端有平坡，如图所示：

上下中间有平坡：

单调有平坡：

数组首尾两端有平坡：

376.摆动序列1

修正判断峰值或峰谷的条件：(preDiff <= 0 && curDiff > 0) || (preDiff >= 0 && curDiff < 0)
preDiff更新时机：我们只需要在这个坡度摆动变化的时候，更新 prediff 就行，这样 preDiff 在单调区间有平坡的时候就不会发生变化，造成我们的误判

代码实现：

class Solution
{public:int wiggleMaxLength(vector<int>& nums){if(nums.size() <= 1){return nums.size();}int curDiff = 0;    // 当前一对差值int preDiff = 0;    // 前一对差值int result = 1;     // 记录峰值个数，默认有一个峰值for(int i=0; i<nums.size()-1; ++i){curDiff = nums[i + 1] - nums[i];// 出现峰值if((preDiff <= 0 && curDiff > 0) || (preDiff >= 0 && curDiff < 0)){result++;preDiff = curDiff;  // 只有在波动时才会更新preDiff}}return result;}
};

53.最大子序和

题目链接：53. 最大子数组和 - 力扣（LeetCode）

思路

可以首先考虑一个较简单的序列，如[-2, 1]，这个序列的最大子序和为1，是从1开始计算的。负数只会拉低总和，因此当“连续和“为负数时应该放弃，而从下一个元素重新开始计算

整体思路：遍历nums数组，sum记录当前的连续和，result记录之前最大的连续和。如果sum>=0，则继续计算连续和，sum += nums[i]；如果sum<0，则需要重新开始计算连续和，sum = nums[i]。如图所示：

53.最大子序和

红色表示连续和

代码实现：

class Solution {
public:int maxSubArray(vector<int>& nums) {int result = nums[0];int sum = 0;for(int num : nums){if(sum >= 0){sum += num;}else{sum = num;}result = max(result, sum);}return result;}
};