代码随想录算法训练营第三十一天 |基础知识，455.分发饼干，376.摆动序列，53.最大子序和（已补充）

你的名字 2024-04-23 04:16 58阅读 0赞

## 基础知识： ##

题目分类大纲如下：

![efcde260e01aaffb70b3c73fc4e08ea8.png][]

### [\#][Link 1]算法公开课 ###

[《代码随想录》算法视频公开课(opens new window)][opens new window]**：**[贪心算法理论基础！(opens new window)][opens new window 1]**,相信结合视频再看本篇题解，更有助于大家对本题的理解**。

### [\#][Link 2]什么是贪心 ###

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

这么说有点抽象，来举一个例子：

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

指定每次拿最大的，最终结果就是拿走最大数额的钱。

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

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

### [\#][Link 3]贪心的套路（什么时候用贪心） ###

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

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

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

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

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

有同学问了如何验证可不可以用贪心算法呢？

**最好用的策略就是举反例，如果想不到反例，那么就试一试贪心吧**。

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

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

*  数学归纳法
 *  反证法

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

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

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

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

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

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

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

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

### [\#][Link 4]贪心一般解题步骤 ###

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

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

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

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

### [\#][Link 5]总结 ###

本篇给出了什么是贪心以及大家关心的贪心算法固定套路。

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

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

## 455.分发饼干（已观看） ##

1、题目链接：[力扣（LeetCode）官网 - 全球极客挚爱的技术成长平台][LeetCode_ -]

2、文章讲解：[代码随想录][Link 6]

3、题目：

假设你是一位很棒的家长，想要给你的孩子们一些小饼干。但是，每个孩子最多只能给一块饼干。

对每个孩子 i，都有一个胃口值 g\[i\]，这是能让孩子们满足胃口的饼干的最小尺寸；并且每块饼干 j，都有一个尺寸 s\[j\] 。如果 s\[j\] >= g\[i\]，我们可以将这个饼干 j 分配给孩子 i ，这个孩子会得到满足。你的目标是尽可能满足越多数量的孩子，并输出这个最大数值。

示例 1:

*  输入: g = \[1,2,3\], s = \[1,1\]
 *  输出: 1 解释:你有三个孩子和两块小饼干，3 个孩子的胃口值分别是：1,2,3。虽然你有两块小饼干，由于他们的尺寸都是 1，你只能让胃口值是 1 的孩子满足。所以你应该输出 1。

示例 2:

*  输入: g = \[1,2\], s = \[1,2,3\]
 *  输出: 2
 *  解释:你有两个孩子和三块小饼干，2 个孩子的胃口值分别是 1,2。你拥有的饼干数量和尺寸都足以让所有孩子满足。所以你应该输出 2.

提示：

*  1 <= g.length <= 3 \* 10^4
 *  0 <= s.length <= 3 \* 10^4
 *  1 <= g\[i\], s\[j\] <= 2^31 - 1

4、视频讲解：

[贪心算法，你想先喂哪个小孩？| LeetCode：455.分发饼干\_哔哩哔哩\_bilibili][LeetCode_455._bilibili]

5、思路：

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

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

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

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

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

如图：

![008b0a82bcacd1b4c5bbc07cc704febf.png][]

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

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

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

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

class Solution {
        // 优先考虑饼干，小饼干先喂饱小胃口
        public int findContentChildren(int[] g, int[] s) {
            Arrays.sort(g);
            Arrays.sort(s);
            int start = 0;
            int count = 0;
            for (int i = 0; i < s.length && start < g.length; i++) {
                if (s[i] >= g[start]) {
                    count++;
                    start++;
                }
            }
            return count;
        }
    }

class Solution {
        // 优先考虑胃口，先喂饱大胃口
        public int findContentChildren(int[] g, int[] s) {
            Arrays.sort(g);
            Arrays.sort(s);
            int start = s.length - 1;
            int count = 0;
            for (int index = g.length - 1; index >= 0; index--) {
                if (start >= 0 && s[start] >= g[index]) {
                    count++;
                    start--;
                }
            }
            return count;
        }
    }

## 376.摆动序列 ##

1、题目链接：[力扣（LeetCode）官网 - 全球极客挚爱的技术成长平台][LeetCode_ - 1]

2、文章讲解：[代码随想录][Link 7]

3、题目：

如果连续数字之间的差严格地在正数和负数之间交替，则数字序列称为摆动序列。第一个差（如果存在的话）可能是正数或负数。少于两个元素的序列也是摆动序列。

例如， \[1,7,4,9,2,5\] 是一个摆动序列，因为差值 (6,-3,5,-7,3) 是正负交替出现的。相反, \[1,4,7,2,5\] 和 \[1,7,4,5,5\] 不是摆动序列，第一个序列是因为它的前两个差值都是正数，第二个序列是因为它的最后一个差值为零。

给定一个整数序列，返回作为摆动序列的最长子序列的长度。 通过从原始序列中删除一些（也可以不删除）元素来获得子序列，剩下的元素保持其原始顺序。

示例 1:

*  输入: \[1,7,4,9,2,5\]
 *  输出: 6
 *  解释: 整个序列均为摆动序列。

示例 2:

*  输入: \[1,17,5,10,13,15,10,5,16,8\]
 *  输出: 7
 *  解释: 这个序列包含几个长度为 7 摆动序列，其中一个可为\[1,17,10,13,10,16,8\]。

示例 3:

*  输入: \[1,2,3,4,5,6,7,8,9\]
 *  输出: 2

4、视频链接：

[贪心算法，寻找摆动有细节！| LeetCode：376.摆动序列\_哔哩哔哩\_bilibili][LeetCode_376._bilibili]

class Solution {
        public int wiggleMaxLength(int[] nums) {
            if (nums.length <= 1) {
                return nums.length;
            }
            // 当前差值
            int curDiff = 0;
            // 上一个差值
            int preDiff = 0;
            // 峰值和谷值的个数
            int count = 1;
            // 遍历数组，从1开始，因为count初始化为1
            for (int i = 1; i < nums.length; i++) {
                // 计算差值
                curDiff = nums[i] - nums[i - 1];
                // 如果当前差值和上一个差值为一正一负
                // 等于0的情况表示这个数和前一个数相等，不影响结果
                if ((curDiff > 0 && preDiff <= 0) || (curDiff < 0 && preDiff >= 0)) {
                    count++;
                    preDiff = curDiff;
                }
            }
            return count;
        }
    }

## 53.最大子序和 ##

1、题目链接：[力扣（LeetCode）官网 - 全球极客挚爱的技术成长平台][LeetCode_ - 2]

2、文章讲解：[代码随想录][Link 8]

3、题目：

给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。

示例:

*  输入: \[-2,1,-3,4,-1,2,1,-5,4\]
 *  输出: 6
 *  解释: 连续子数组 \[4,-1,2,1\] 的和最大，为 6。

4、视频链接：

[贪心算法的巧妙需要慢慢体会！LeetCode：53. 最大子序和\_哔哩哔哩\_bilibili][LeetCode_53. _bilibili]

5、思路：

#### 暴力解法 ####

暴力解法的思路，第一层 for 就是设置起始位置，第二层 for 循环遍历数组寻找最大值

class Solution {
    public:
        int maxSubArray(vector<int>& nums) {
            int result = INT32_MIN;
            int count = 0;
            for (int i = 0; i < nums.size(); i++) { // 设置起始位置
                count = 0;
                for (int j = i; j < nums.size(); j++) { // 每次从起始位置i开始遍历寻找最大值
                    count += nums[j];
                    result = count > result ? count : result;
                }
            }
            return result;
        }
    };

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

以上暴力的解法 C++勉强可以过，其他语言就不确定了。

#### [\#][Link 9]贪心解法 ####

**贪心贪的是哪里呢？**

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

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

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

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

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

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

**那有同学问了，区间终止位置不用调整么？ 如何才能得到最大“连续和”呢？**

区间的终止位置，其实就是如果 count 取到最大值了，及时记录下来了。例如如下代码：

if (count > result) result = count;

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

如动画所示：

![e1406c9ac6ec19511350464267097970.gif][]

红色的起始位置就是贪心每次取 count 为正数的时候，开始一个区间的统计。

那么不难写出如下 C++代码（关键地方已经注释）

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

*  时间复杂度：O(n)
 *  空间复杂度：O(1)

当然题目没有说如果数组为空，应该返回什么，所以数组为空的话返回啥都可以了。

#### 常见误区 ####

误区一：

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

误区二：

大家在使用贪心算法求解本题，经常陷入的误区，就是分不清，是遇到 负数就选择起始位置，还是连续和为负选择起始位置。

在动画演示用，大家可以发现， 4，遇到 -1 的时候，我们依然累加了，为什么呢？

因为和为 3，**只要连续和还是正数就会 对后面的元素 起到增大总和的作用**。 所以只要连续和为正数我们就保留。

这里也会有录友疑惑，那 4 + -1 之后 不就变小了吗？ 会不会错过 4 成为最大连续和的可能性？

其实并不会，因为还有一个变量 result 一直在更新 最大的连续和，只要有更大的连续和出现，result 就更新了，那么 result 已经把 4 更新了，后面 连续和变成 3，也不会对最后结果有影响。

class Solution {
        public int maxSubArray(int[] nums) {
            if (nums.length == 1) {
                return nums[0];
            }
            int sum = Integer.MIN_VALUE;
            int count = 0;
            for (int i = 0; i < nums.length; i++) {
                count += nums[i];
                // 取区间累计的最大值
                sum = Math.max(count, sum);
                // 剪枝，如果当前累加和已经小于0，那么后面无论再怎么加，结果都不会比当前sum大了
                if (count < 0) {
                    count = 0;
                }
            }
            return sum;
        }
    }

[efcde260e01aaffb70b3c73fc4e08ea8.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/23/27075cc97f344cef86fbde7acb841823.png
[Link 1]: https://www.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#%E7%AE%97%E6%B3%95%E5%85%AC%E5%BC%80%E8%AF%BE
[opens new window]: https://programmercarl.com/other/gongkaike.html
[opens new window 1]: https://www.bilibili.com/video/BV1WK4y1R71x/
[Link 2]: https://www.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#%E4%BB%80%E4%B9%88%E6%98%AF%E8%B4%AA%E5%BF%83
[Link 3]: https://www.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#%E8%B4%AA%E5%BF%83%E7%9A%84%E5%A5%97%E8%B7%AF-%E4%BB%80%E4%B9%88%E6%97%B6%E5%80%99%E7%94%A8%E8%B4%AA%E5%BF%83
[opens new window 2]: https://programmercarl.com/0142.%E7%8E%AF%E5%BD%A2%E9%93%BE%E8%A1%A8II.html
[Link 4]: https://www.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#%E8%B4%AA%E5%BF%83%E4%B8%80%E8%88%AC%E8%A7%A3%E9%A2%98%E6%AD%A5%E9%AA%A4
[Link 5]: https://www.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#%E6%80%BB%E7%BB%93
[LeetCode_ -]: https://leetcode.cn/problems/assign-cookies/
[Link 6]: https://www.programmercarl.com/0455.%E5%88%86%E5%8F%91%E9%A5%BC%E5%B9%B2.html#%E7%AE%97%E6%B3%95%E5%85%AC%E5%BC%80%E8%AF%BE
[LeetCode_455._bilibili]: https://www.bilibili.com/video/BV1MM411b7cq
[008b0a82bcacd1b4c5bbc07cc704febf.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/23/675ed498f9a54cca95164d24b3ad56bb.png
[LeetCode_ - 1]: https://leetcode.cn/problems/wiggle-subsequence/
[Link 7]: https://www.programmercarl.com/0376.%E6%91%86%E5%8A%A8%E5%BA%8F%E5%88%97.html#%E7%AE%97%E6%B3%95%E5%85%AC%E5%BC%80%E8%AF%BE
[LeetCode_376._bilibili]: https://www.bilibili.com/video/BV17M411b7NS
[LeetCode_ - 2]: https://leetcode.cn/problems/maximum-subarray/
[Link 8]: https://www.programmercarl.com/0053.%E6%9C%80%E5%A4%A7%E5%AD%90%E5%BA%8F%E5%92%8C.html#%E7%AE%97%E6%B3%95%E5%85%AC%E5%BC%80%E8%AF%BE
[LeetCode_53. _bilibili]: https://www.bilibili.com/video/BV1aY4y1Z7ya
[Link 9]: https://www.programmercarl.com/0053.%E6%9C%80%E5%A4%A7%E5%AD%90%E5%BA%8F%E5%92%8C.html#%E8%B4%AA%E5%BF%83%E8%A7%A3%E6%B3%95
[e1406c9ac6ec19511350464267097970.gif]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/23/ec51077a11514b0ca3a18cd895347d57.gif