代码随想录day31｜开始贪心咯｜贪心理论｜455.分发饼干｜376. 摆动序列｜53. 最大子序和｜复习day2｜Golang

代码随想录day31

事已过半

目录

贪心基础理论：

455.分发饼干

376. 摆动序列

53. 最大子序和

今天小结：

---

贪心基础理论：

什么是贪心

        贪心的本质是选择每一阶段的局部最优，从而达到全局最优。这么说有点抽象，来举一个例子：

        例如，有一堆钞票，你可以拿走十张，如果想达到最大的金额，你要怎么拿？

        指定每次拿最大的，最终结果就是拿走最大数额的钱。每次拿最大的就是局部最优，最后拿走最大数额的钱就是推出全局最优。

        再举一个例子如果是 有一堆盒子，你有一个背包体积为n，如何把背包尽可能装满，如果还每次选最大的盒子，就不行了。这时候就需要动态规划。动态规划的问题在下一个系列会详细讲解。

贪心的套路（什么时候用贪心）

        很多同学做贪心的题目的时候，想不出来是贪心，想知道有没有什么套路可以一看就看出来是贪心。说实话贪心算法并没有固定的套路。

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

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

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

        有同学问了如何验证可不可以用贪心算法呢？最好用的策略就是举反例，如果想不到反例，那么就试一试贪心吧。

        可有有同学认为手动模拟，举例子得出的结论不靠谱，想要严格的数学证明。

一般数学证明有如下两种方法：

• 数学归纳法
• 反证法

        看教课书上讲解贪心可以是一堆公式，估计大家连看都不想看，所以数学证明就不在我要讲解的范围内了，大家感兴趣可以自行查找资料。

        面试中基本不会让面试者现场证明贪心的合理性，代码写出来跑过测试用例即可，或者自己能自圆其说理由就行了。

        举一个不太恰当的例子：我要用一下1+1 = 2，但我要先证明1+1 为什么等于2。严谨是严谨了，但没必要。

        虽然这个例子很极端，但可以表达这么个意思：刷题或者面试的时候，手动模拟一下感觉可以局部最优推出整体最优，而且想不到反例，那么就试一试贪心。

        例如刚刚举的拿钞票的例子，就是模拟一下每次拿做大的，最后就能拿到最多的钱，这还要数学证明的话，其实就不在算法面试的范围内了，可以看看专业的数学书籍！

        所以这也是为什么很多同学通过（accept）了贪心的题目，但都不知道自己用了贪心算法，因为贪心有时候就是常识性的推导，所以会认为本应该就这么做！

        那么刷题的时候什么时候真的需要数学推导呢？

        例如这道题目：链表：环找到了，那入口呢？，这道题不用数学推导一下，就找不出环的起始位置，想试一下就不知道怎么试，这种题目确实需要数学简单推导一下。

贪心一般解题步骤

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

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

        其实这个分的有点细了，真正做题的时候很难分出这么详细的解题步骤，可能就是因为贪心的题目往往还和其他方面的知识混在一起。

小结

        本篇给出了什么是贪心以及大家关心的贪心算法固定套路。不好意思了，贪心没有套路，说白了就是常识性推导加上举反例。

        最后给出贪心的一般解题步骤，大家可以发现这个解题步骤也是比较抽象的，不像是二叉树，回溯算法，给出了那么具体的解题套路和模板。

        本篇没有配图，其实可以找一些动漫周边或者搞笑的图配一配（符合大多数公众号文章的作风），但这不是我的风格，所以本篇文字描述足以！

455.分发饼干

思路

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

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

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

        可以尝试使用贪心策略，先将饼干数组和小孩数组排序。然后从后向前遍历小孩数组，用大饼干优先满足胃口大的，并统计满足小孩数量。

如图：

        这个例子可以看出饼干9只有喂给胃口为7的小孩，这样才是整体最优解，并想不出反例，那么就可以撸代码了。 

func findContentChildren(g []int, s []int) int {
    sort.Ints(g)    // 排序一下胃
    sort.Ints(s)    // 排序一下饼干
    s_i := len(s)-1 // 最大的饼干下标
    childCount := 0
 
    for i:=len(g)-1;i>=0;i--{   //遍历胃口
        if s_i >=0 && s[s_i] >= g[i] {  // 如果最大的饼干可以满足最大的胃口
            childCount++    // 计数，满足的孩子
            s_i--   // 最大的饼干消耗完啦，左移到次大饼干
        }
    }
    return childCount   // 返回被满足的孩子数量捏。
}

也可以换个思路，小饼干喂小胃口。

/*
g[child]    // 第child被满足孩子的胃口
s[s_i]  // 第s_i个饼干
*/
 
//排序后局部最优，用小饼干喂小胃口的孩子
func findContentChildren(g []int, s []int) int {
    sort.Ints(g)    // 排序一下胃口
    sort.Ints(s)    // 排序一下饼干
    child := 0  // 初始化第child个孩子下标
    for s_i:=0;s_i < len(s) && child < len(g);s_i++{
        if s[s_i] >= g[child] {
            child++     // 巧妙用child，这样既可能计数，又可以找下一个孩子的胃
        }
    }
    return child    // 返回被满足的child数量
}

本题小结

        这道题是贪心很好的一道入门题目，思路还是比较容易想到的。

        文中详细介绍了思考的过程，想清楚局部最优，想清楚全局最优，感觉局部最优是可以推出全局最优，并想不出反例，那么就试一试贪心。

376. 摆动序列

进阶：你能否用 O(n) 时间复杂度完成此题?

思路1（贪心解法）

        本题要求通过从原始序列中删除一些（也可以不删除）元素来获得子序列，剩下的元素保持其原始顺序。

        相信这么一说吓退不少同学，这要求最大摆动序列又可以修改数组，这得如何修改呢？

        来分析一下，要求删除元素使其达到最大摆动序列，应该删除什么元素呢？

用示例二来举例，如图所示：

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

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

        局部最优推出全局最优，并举不出反例，那么试试贪心！（为方便表述，以下说的峰值都是指局部峰值）

        实际操作上，其实连删除的操作都不用做，因为题目要求的是最长摆动子序列的长度，所以只需要统计数组的峰值数量就可以了（相当于是删除单一坡度上的节点，然后统计长度）

        这就是贪心所贪的地方，让峰值尽可能的保持峰值，然后删除单一坡度上的节点。

        本题代码实现中，还有一些技巧，例如统计峰值的时候，数组最左面和最右面是最不好统计的。

        例如序列[2,5]，它的峰值数量是2，如果靠统计差值来计算峰值个数就需要考虑数组最左面和最右面的特殊情况。

        所以可以针对序列[2,5]，可以假设为[2,2,5]，这样它就有坡度了即preDiff = 0，如图：

        针对以上情形，result初始为1（默认最右面有一个峰值），此时curDiff > 0 && preDiff <= 0，那么result++（计算了左面的峰值），最后得到的result就是2（峰值个数为2即摆动序列长度为2） 所以对应的go语言代码如下：

func wiggleMaxLength(nums []int) int {
    count, pre, cur := 1, 0, 0 
    if len(nums) < 2 {  // 有一个元素或者含两个不等元素的序列也视作摆动序列。
        return 1    
    }
    for i:=1;i<len(nums);i++{
        cur = nums[i] - nums[i-1] 
        if cur > 0 && pre <= 0 || cur < 0 && pre >= 0 {
            count++
            pre = cur   // 更新pre
        }
    }
    return count
}
 
// 不明白就自己举个示例演算一下

本题小结：

        贪心的题目说简单有的时候就是常识，说难就难在都不知道该怎么用贪心。

        本题大家如果要去模拟删除元素达到最长摆动子序列的过程，那指定绕里面去了，一时半会拔不出来。

        而这道题目有什么技巧说一下子能想到贪心么？其实也没有，类似的题目做过了就会想到。此时大家就应该了解了：保持区间波动，只需要把单调区间上的元素移除就可以了。

53. 最大子序和

 进阶：如果你已经实现复杂度为 O(n) 的解法，尝试使用更为精妙的 分治法 求解。

暴力解法

        暴力解法的思路，第一层for 就是设置起始位置，第二层for循环遍历数组寻找最大值。这道题C++的暴力可以过，Go语言的暴力过不了，会超时。

• 时间复杂度：O(n^2)
• 空间复杂度：O(1)

func maxSubArray(nums []int) int {
    result := math.Inf(-1)
    var count float64
    for i:=0;i<len(nums);i++{
        count = 0
        for j:=i;j<len(nums);j++{
            count += float64(nums[j])
            if count > result {
                result = count
            }
        }
    }
    return int(result)
}
//会超时

贪心解法

        贪心贪的是哪里呢？

        如果 -2 1 在一起，计算起点的时候，一定是从1开始计算，因为负数只会拉低总和，这就是贪心贪的地方！

        局部最优：当前“连续和”为负数的时候立刻放弃，从下一个元素重新计算“连续和”，因为负数加上下一个元素 “连续和”只会越来越小。

        全局最优：选取最大“连续和”。

        局部最优的情况下，并记录最大的“连续和”，可以推出全局最优。

        从代码角度上来讲：遍历nums，从头开始用count累积，如果count一旦加上nums[i]变为负数，那么就应该从nums[i+1]开始从0累积count了，因为已经变为负数的count，只会拖累总和。

        这相当于是暴力解法中的不断调整最大子序和区间的起始位置。

        那有同学问了，区间终止位置不用调整么？ 如何才能得到最大“连续和”呢？区间的终止位置，其实就是如果count取到最大值了，及时记录下来了。例如如下代码：

if count > result {
    result = count
}

这样相当于是用result记录最大子序和区间和（变相的算是调整了终止位置）。

如动画所示：

        红色的起始位置就是贪心每次取count为正数的时候，开始一个区间的统计。那么不难写出如下Go代码（关键地方已经注释）

func maxSubArray(nums []int) int {
    result := math.Inf(-1)
    var count float64
    for i:=0;i<len(nums);i++{
        count += float64(nums[i])
        if count > result {   // 取区间累计的最大值（相当于不断确定最大子序终止位置）
            result = count   
        }
        if count <= 0 {    // 相当于重置最大字序起始位置，因为遇到负数一定是拉低总和。
            count = 0
        }
    }
    return int(result)
}
时间复杂度：O(n)
空间复杂度：O(1)

        不少同学认为 如果输入用例都是-1，或者 都是负数，这个贪心算法跑出来的结果是0， 这是又一次证明脑洞模拟不靠谱的经典案例，建议大家把代码运行一下试一试，就知道了，也会理解 为什么 result 要初始化为最小负数了。

哈哈哈哈哈哈。如果输入用例是-1，
那么count = -1
那么 count > result(无穷小)
那么 result = -1
那么 count <= 0
那么 count = 0
那么 return 的是result = -1啊

总结

        本题的贪心思路其实并不好想，这也进一步验证了，别看贪心理论很直白，有时候看似是常识，但贪心的题目一点都不简单！后续将介绍的贪心题目都挺难的，哈哈，所以贪心很有意思，别小看贪心！

今天小结：

        开始了贪心算法，在关于贪心算法，你该了解这些！中，我们介绍了什么是贪心以及贪心的套路。

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

有没有啥套路呢？

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

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

• 数学归纳法
• 反证法

        数学就不在讲解范围内了，感兴趣的同学可以自己去查一查资料。正是因为贪心算法有时候会感觉这是常识，本就应该这么做！ 所以大家经常看到网上有人说这是一道贪心题目，有人是这不是。

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

        在贪心算法：分发饼干中讲解了贪心算法的第一道题目。这道题目很明显能看出来是用贪心，也是入门好题。

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

        很多录友都是用小饼干优先先喂饱小胃口的。后来我想一想，虽然结果是一样的，但是大家的这个思考方式更好一些。

        因为用小饼干优先喂饱小胃口的 这样可以尽量保证最后省下来的是大饼干（虽然题目没有这个要求）！所有还是小饼干优先先喂饱小胃口更好一些，也比较直观。

一些录友不清楚贪心算法：分发饼干中时间复杂度是怎么来的？就是快排O(nlog n)，遍历O(n)，加一起就是还是O(nlogn)。

        接下来就要上一点难度了，要不然大家会误以为贪心算法就是常识判断一下就行了。在贪心算法：摆动序列中，需要计算最长摇摆序列。

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

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

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

        在计算峰值的时候，还是有一些代码技巧的，例如序列两端的峰值如何处理。这些技巧，其实还是要多看多用才会掌握。

        在贪心算法：最大子序和中，详细讲解了用贪心的方式来求最大子序列和，其实这道题目是一道动态规划的题目。

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

        代码很简单，但是思路却比较难。还需要反复琢磨。针对贪心算法：最大子序和 文章中给出的贪心代码如下；

        不少同学都来问，如果数组全是负数这个代码就有问题了，如果数组里有int最小值这个代码就有问题了。大家不要脑洞模拟哈，可以亲自构造一些测试数据试一试，就发现其实没有问题。数组都为负数，result记录的就是最小的负数，如果数组里有int最小值，那么最终result就是int最小值。

        今天我们讲解了贪心算法的理论基础了解了贪心本质：局部最优推出全局最优。然后讲解了第一道题目分发饼干还是比较基础的，可能会给大家一种贪心算法比较简单的错觉，因为贪心有时候接近于常识。

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

        所以我在贪心系列难度会有所交替，难的题目在于拓展思路，简单的题目在于分析清楚其贪心的本质，后续我还会发一些简单的题目来做贪心的分析。在摆动序列中大家就初步感受到贪心没那么简单了。本周最后是最大子序和，这道题目要用贪心的方式做出来，就比较有难度，都知道负数加上正数之后会变小，但是这道题目依然会让很多人搞混淆，其关键在于：不能让“连续和”为负数的时候加上下一个元素，而不是 不让“连续和”加上一个负数。这块真的需要仔细体会！

复习day2

        自己翻翻day2的内容，做一遍题哦