代码随想录31——贪心：贪心算法理论基础、455分发饼干、376摆动序列

1.贪心算法理论基础

参考：代码随想录，贪心算法理论基础

1.1.题目分类

1.2.贪心算法

1.2.1.什么是贪心算法

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

这么说有点抽象，来举一个例子：例如，有一堆钞票，你可以拿走十张，如果想达到最大的金额，你要怎么拿？

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

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

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

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

说实话贪心算法并没有固定的套路。所以唯一的难点就是如何通过局部最优，推出整体最优。

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

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

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

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

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

1.2.3.贪心一般解题步骤

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

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

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

贪心没有套路，说白了就是常识性推导加上举反例。最后给出贪心的一般解题步骤，大家可以发现这个解题步骤也是比较抽象的，不像是二叉树，回溯算法，给出了那么具体的解题套路和模板。

2.455分发饼干

参考：代码随想录，455分发饼干，力扣题目链接

2.1.题目

2.2.解答

为了满足更多的小孩，就不要造成饼干尺寸的浪费。即未给孩子的饼干，应该是满足它的胃口的饼干中最小的那个。

所以这里的局部最优就是从小饼干开始遍历，然后一旦找到可以满足胃口的孩子，就把这个小饼干喂给这个孩子。因此需要先把孩子胃口和饼干大小都进行升序排列。

代码如下所示，非常假单：

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++)
    {
        // 首先index < g.size()保证还有没喂的孩子，防止饼干个数过多，超过孩子总数
        // 遍历所有饼干，只要当前饼干可以喂饱当前孩子，就使用这个饼干；然后继续遍历下一个饼干，喂下一个孩子
        if(index < g.size() && g[index] <= s[i])
            index++;
    }

    return index;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

3.376摆动序列 思路不是很清晰

参考：代码随想录，376摆动序列，力扣题目链接

3.1.题目

3.2.解答

这道题目其实就是在找符合条件的每一个小的坡度。比如上一次是在上升，那么这一次就必须下降。把上升和下降的各个峰值点连接起来，峰值点的个数就是摆动数组的长度。如下图所示：

给出代码如下，还不是很清晰，这个是自己写的，跟代码随想录中有点不一样。

下面代码的思路是先找到第一个有坡度的两个山峰，比如上图的1->17。此时把这个坡度给1，认为每一条线条（每一个坡度）都是属于它的前一个点的。

找到第一个有坡度的山峰之后，我们就有了上一个坡度pre_diff。然后遍历后面的点，开始寻找和上一次的坡度不同的坡度。直到找完所有的山峰。

最后，由于我们统计的是坡度，而每个坡度认为属于它连接的前面的山峰，所以山峰个数 = 坡度个数 + 1。

int wiggleMaxLength(vector<int> &nums)
{
    if(nums.size() < 2)
        return nums.size();
    
    // 先找第一个峰值
    int left = 0;
    int pre_diff = 0; // 前一个坡度
    int result = 0;   // 统计的坡度个数

    while(left < nums.size() - 1)
    {
        if(nums[left] != nums[left+1])
        {
            pre_diff = nums[left + 1] - nums[left];
            result = 1;
            break;
        }
        left++;
    }

    // 再找后面的峰值
    while(left < nums.size() - 1)
    {
        int cur_diff = nums[left + 1] - nums[left];
        if((cur_diff > 0 && pre_diff < 0) || (cur_diff < 0 && pre_diff > 0))
        {
            result++;
            pre_diff = cur_diff;
        }
        left++;
    }

    return result + 1;   // 山峰个数 = 坡度个数 + 1
    
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36