leetcode算法刷题的第二十三天

今天是贪心算法。贪心算法其实没有什么规律可言，所以大家了解贪心算法就了解它没有规律的本质就可以了。没有思路就去看题解，要么就是特别简单，要么就是特别难，非常极端。

1.理论基础

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

很多人开始做贪心的题目的时候，想不出来是贪心，想知道有没有什么套路可以一看就看出来是贪心。

说实话贪心算法并没有固定的套路。

所以唯一的难点就是如何通过局部最优，推出整体最优。

那么如何能看出局部最优是否能推出整体最优呢？有没有什么固定策略或者套路呢？

不好意思，也没有！ 靠自己手动模拟，如果模拟可行，就可以试一试贪心策略，如果不可行，可能需要动态规划。

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

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

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

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

不好意思了，贪心没有套路，说白了就是常识性推导加上举反例。

2.leetcode 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;}
};

思路总结：

为了满足更多的小孩，就不要造成饼干尺寸的浪费。

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

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

可以尝试使用贪心策略，先将饼干数组和小孩数组排序。

然后从后向前遍历小孩数组，用大饼干优先满足胃口大的，并统计满足小孩数量。

从代码中可以看出我用了一个 index 来控制饼干数组的遍历，遍历饼干并没有再起一个 for 循环，而是采用自减的方式，这也是常用的技巧。

有的人看到要遍历两个数组，就想到用两个 for 循环，那样逻辑其实就复杂了。

3.leetcode 376.摆动序列

题目链接

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;}
};

思路总结：

其实本题看起来好像简单，但需要考虑的情况还是很复杂的，而且很难一次性想到位。

本题异常情况的本质，就是要考虑平坡， 平坡分两种，一个是 上下中间有平坡，一个是单调有平坡。

4.leetcode 53.最大子数组和

题目链接

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;// 相当于重置最大子序起始位置，因为遇到负数一定是拉低总和}return result;}
};

思路总结：这道题的贪心策略就是当如果前面的数字加起来是负数的话，就要果断放弃，从下一个数开始遍历，因为如果前面的和是负数的话，加上下一个数，会拖累本身这个数字，肯定是不利于求出最大子数组和，所以当和为负数的时候果断放弃，重新count等于0，然后重新相加这个数组每个数字的和。本题的贪心思路其实并不好想，这也进一步验证了，别看贪心理论很直白，有时候看似是常识，但贪心的题目一点都不简单！