# 本周小结!(贪心算法系列一)

# 周一

本周正式开始了贪心算法,在关于贪心算法,你该了解这些! (opens new window)中,我们介绍了什么是贪心以及贪心的套路。

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

有没有啥套路呢?

不好意思,贪心没套路,就刷题而言,如果感觉好像局部最优可以推出全局最优,然后想不到反例,那就试一试贪心吧!

而严格的数据证明一般有如下两种:

  • 数学归纳法
  • 反证法

数学就不在讲解范围内了,感兴趣的同学可以自己去查一查资料。

正式因为贪心算法有时候会感觉这是常识,本就应该这么做! 所以大家经常看到网上有人说这是一道贪心题目,有人是这不是。

这里说一下我的依据:如果找到局部最优,然后推出整体最优,那么就是贪心,大家可以参考哈。

# 周二

贪心算法:分发饼干 (opens new window)中讲解了贪心算法的第一道题目。

这道题目很明显能看出来是用贪心,也是入门好题。

我在文中给出局部最优:大饼干喂给胃口大的,充分利用饼干尺寸喂饱一个,全局最优:喂饱尽可能多的小孩

很多录友都是用小饼干优先先喂饱小胃口的。

后来我想一想,虽然结果是一样的,但是大家的这个思考方式更好一些。

因为用小饼干优先喂饱小胃口的 这样可以尽量保证最后省下来的是大饼干(虽然题目没有这个要求)!

所有还是小饼干优先先喂饱小胃口更好一些,也比较直观。

一些录友不清楚贪心算法:分发饼干 (opens new window)中时间复杂度是怎么来的?

就是快排O(nlogn),遍历O(n),加一起就是还是O(nlogn)。

# 周三

接下来就要上一点难度了,要不然大家会误以为贪心算法就是常识判断一下就行了。

贪心算法:摆动序列 (opens new window)中,需要计算最长摇摆序列。

其实就是让序列有尽可能多的局部峰值。

局部最优:删除单调坡度上的节点(不包括单调坡度两端的节点),那么这个坡度就可以有两个局部峰值。

整体最优:整个序列有最多的局部峰值,从而达到最长摆动序列。

在计算峰值的时候,还是有一些代码技巧的,例如序列两端的峰值如何处理。

这些技巧,其实还是要多看多用才会掌握。

# 周四

贪心算法:最大子序和 (opens new window)中,详细讲解了用贪心的方式来求最大子序列和,其实这道题目是一道动态规划的题目。

贪心的思路为局部最优:当前“连续和”为负数的时候立刻放弃,从下一个元素重新计算“连续和”,因为负数加上下一个元素 “连续和”只会越来越小。从而推出全局最优:选取最大“连续和”

代码很简单,但是思路却比较难。还需要反复琢磨。

针对贪心算法:最大子序和 (opens new window)文章中给出的贪心代码如下;

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;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

不少同学都来问,如果数组全是负数这个代码就有问题了,如果数组里有int最小值这个代码就有问题了。

大家不要脑洞模拟哈,可以亲自构造一些测试数据试一试,就发现其实没有问题。

数组都为负数,result记录的就是最小的负数,如果数组里有int最小值,那么最终result就是int最小值。

# 总结

本周我们讲解了贪心算法的理论基础 (opens new window),了解了贪心本质:局部最优推出全局最优。

然后讲解了第一道题目分发饼干 (opens new window),还是比较基础的,可能会给大家一种贪心算法比较简单的错觉,因为贪心有时候接近于常识。

其实我还准备一些简单的贪心题目,甚至网上很多都质疑这些题目是不是贪心算法。这些题目我没有立刻发出来,因为真的会让大家感觉贪心过于简单,而忽略了贪心的本质:局部最优和全局最优两个关键点。

所以我在贪心系列难度会有所交替,难的题目在于拓展思路,简单的题目在于分析清楚其贪心的本质,后续我还会发一些简单的题目来做贪心的分析。

摆动序列 (opens new window)中大家就初步感受到贪心没那么简单了。

本周最后是最大子序和 (opens new window),这道题目要用贪心的方式做出来,就比较有难度,都知道负数加上正数之后会变小,但是这道题目依然会让很多人搞混淆,其关键在于:不能让“连续和”为负数的时候加上下一个元素,而不是 不让“连续和”加上一个负数。这块真的需要仔细体会!