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

贪心算法理论基础

什么是贪心？

什么时候用贪心？

455.分发饼干

前言

思路

算法实现

376. 摆动序列

前言

算法实现

53. 最大子序和

方法一：暴力解法

方法二：贪心算法

总结

贪心算法理论基础

文章链接https://programmercarl.com/%E8%B4%AA%E5%BF%83%E7%AE%97%E6%B3%95%E7%90%86%E8%AE%BA%E5%9F%BA%E7%A1%80.html

什么是贪心？

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

什么时候用贪心？

如果该问题能够通过拆分成局部最优从而得到全局最优并且举不出明显的反例，那么就可以用贪心算法。对于贪心算法的具体实现，不同题目有不同的具体实现，没有统一的模板，所以得结合具体的题目学习。

455.分发饼干

题目链接

文章链接

前言

本题要使不同大小的饼干和胃口之间得到合理的分配，为了满足更多的小孩，就不要造成饼干尺寸的浪费。大尺寸的饼干既可以满足胃口大的孩子也可以满足胃口小的孩子，那么就应该优先满足胃口大的（或者小尺寸的饼干优先分给胃口小的）。

思路

参照上面大饼干喂给大胃口的思路，这里的局部最优就是大饼干喂给胃口大的，充分利用饼干尺寸喂饱一个，全局最优就是喂饱尽可能多的小孩。可以尝试使用贪心策略，先将饼干数组和小孩数组排序。然后从后向前遍历小孩数组，用大饼干优先满足胃口大的，并统计满足小孩数量。

算法实现

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

也可以使用第二种思路（小尺寸的饼干先分给胃口小的），这种方式要依次遍历饼干数组，统计满足条件的饼干个数，直接返回满足条件的饼干数即可。

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. 摆动序列

题目链接

文章链接

前言

本题要求通过从原始序列中删除一些（也可以不删除）元素来获得子序列，剩下的元素保持其原始顺序。如果能够画出序列上下摆动的坡度图就能很好理解。

局部最优：删除单调坡度上的节点（不包括单调坡度两端的节点），那么这个坡度就可以有两个局部峰值。整体最优：整个序列有最多的局部峰值，从而达到最长摆动序列。

在实际操作上并不需要删除的操作，因为只要求最长摆动序列的长度，所以只需要统计数组的峰值数量就可以。因此目的是让峰值尽可能的保持峰值，然后删除单一坡度上的节点。

在计算是否有峰值的时候，通过计算当前值和前一个节点值的差值prediff(nums[i] - nums[i - 1]) 和当前值与下一个节点值的差值curdiff(nums[i + 1] - nums[i])，如果prediff(nums[i] - nums[i - 1]) < 0 && curdiff(nums[i + 1] - nums[i]) > 0 或者 prediff(nums[i] - nums[i - 1]) > 0 && curdiff(nums[i + 1] - nums[i]) < 0，此时就有波动（峰值）需要统计。

以上分析是大体思路，但是还要考虑三种情况：

情况一：上下坡中有平坡；
情况二：数组的首尾两端；
情况三：单调坡中有平坡；

为了解决第一种情况，在平坡中我们只针对一个元素做处理，不考虑其余相同元素，统一规则只看平坡最右侧的元素，此时对峰值波动的统计规则则改为 prediff <= 0 && curdiff > 0 或者 prediff >= 0 && curdiff < 0。

对于第二种情况，我们以上的分析都是针对数组有三个数字以上的，对于一个元素的数组我们可以直接返回它的大小（符合题目条件），对于两个元素的数组，，结构为2，可以直接写死，当两个元素不相同时直接返回2，也可以按照上述条件来，对于第一个元素，当做它前面有一个平坡，相当于preDiff = 0，对于末尾元素，可以默认序列最右边有一个峰值，即result从一开始计数。

对于第三种情况，只要更改preDiff和curDiff的赋值位置就可以，不要在每次循环中事实更新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;}}return result;}
};

53. 最大子序和

题目链接

文章链接

方法一：暴力解法

class Solution {
public:int maxSubArray(vector<int>& nums) {int result = INT_MIN;int sum = 0;for (int i = 0; i < nums.size(); i++){sum = 0;for (int j = i; j < nums.size(); j++){sum += nums[j];result = (result > sum ? result : sum); }}return result;}
};

本题的暴力解法还是很好想的，两层for循环，第一层依次向前遍历数组元素，第二层加上符合条件的数组元素，在遍历每一次元素时要重新将总和sum置零，从新向后累加数组的值，然后判断新的sum值和之前记录的result值哪个大再进行重新赋值。

方法二：贪心算法

class Solution {
public:int maxSubArray(vector<int>& nums) {int result = INT_MIN;int sum = 0;for (int i = 0; i < nums.size(); i++){sum += nums[i];if (sum > result){result = sum;}if (sum < 0) sum = 0;}return result;}
};

本题的贪心实现较为巧妙，如果当前累加的sum值已经小于0，那么加上后面的值只会使后面的值更小，因此直接重新归0，从下一个值重新求和，然后在判断每次记录的result值和新的sum值哪个更大，记录较大值。