本文是基本常见的贪心算法题解

一、贪心算法简介

贪心无套路.

思考局部最优解是什么, 然后思考局部最优能不能推出全局最优(没有严格证明, 就是感觉局部最优可以推理出全局最优,同时自己还想不到反例, 那么就可以试一试贪心的策略, 仅仅是尝试)

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

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

这个四步其实过于理论化了，只要想清楚 局部最优 是什么，如果推导出全局最优，其实就够了.

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

二、贪心算法题解

455. 分发饼干

小饼干先喂饱小胃口

大饼干先喂饱大胃口

这两种思路都可以

下面是leetcode的解法,我第一次写也是这样的.方便好理解.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
    int findContentChildren(vector<int> &g, vector<int> &s) {
        int ret = 0; // 初始时默认满足0个孩子
        sort(g.begin(), g.end());
        sort(s.begin(), s.end());
        int n = g.size(), m = s.size();
        int i = 0, j = 0;
        while (i < n && j < m) {
            // g是胃口值,s是尺寸
            if (s[j] >= g[i]) {
                ret++;
                i++;
                j++;
            } else {
                j++;
            }
        }
        return ret;
    }
};

376. 摆动序列

这题的贪心方法

本题要考虑三种情况：

  1. 情况一：上下坡中有平坡
  2. 情况二：数组首尾两端
  3. 情况三：单调坡中有平坡
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
    int wiggleMaxLength(vector<int> &nums) {
        int n = nums.size();
        // 按照代码随想录的思路来写
        if (n < 2) {
            return n;
        }
        // 长度为2也囊括在后面的代码判断里面
        int ret = 1;     // 默认最右端是有一个坡度的.
        int prediff = 0; // 最左段向前延长.
        int curdiff = 0; // 因为curdiff后面会改值,所以初始为多少都无所谓
        for (int i = 0; i < n - 1; i++) {
            curdiff = nums[i + 1] - nums[i];
            if ((curdiff > 0 && prediff <= 0) || (curdiff < 0 && prediff >= 0)) {
                ret++;
                prediff = curdiff;
            }
        }
        return ret;
    }
};

leetcode题解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    int wiggleMaxLength(vector<int> &nums) {
        int n = nums.size();
        // leetcode的思路
        if (n < 2) {
            return n;
        }
        int prevdiff = nums[1] - nums[0];//这里的prevdiff也有可能是0
        int ret = prevdiff != 0 ? 2 : 1;
        for (int i = 1; i < n - 1; i++) {
            int curdiff = nums[i + 1] - nums[i];
            if ((curdiff > 0 && prevdiff <= 0) || (curdiff < 0 && prevdiff >= 0)) {
                ret++;
                prevdiff = curdiff;
            }
        }
        return ret;
    }
};

或者这样写(都是一样的)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    int wiggleMaxLength(vector<int> &nums) {
        int n = nums.size();
        // leetcode的思路
        if (n < 2) {
            return n;
        }
        int prevdiff = nums[1] - nums[0];//这里的prevdiff也有可能是0
        int ret = prevdiff != 0 ? 2 : 1;
        for (int i = 2; i < n; i++) {
            int curdiff = nums[i] - nums[i - 1];
            if ((curdiff > 0 && prevdiff <= 0) || (curdiff < 0 && prevdiff >= 0)) {
                ret++;
                prevdiff = curdiff;
            }
        }
        return ret;
    }
};

53. 最大子数组和

暴力解法

超出了时间限制, 但是逻辑肯定是没问题的

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    int maxSubArray(vector<int> &nums) {
        // 暴力写法
        int ret = INT_MIN;
        int n = nums.size();
        for (int i = 0; i < n; i++) {
            int count = 0;
            for (int j = i; j < n; j++) {
                count += nums[j];
                ret = ret > count ? ret : count;
            }
        }
        return ret;
    }
};

贪心思路

贪心贪的是哪里呢？

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

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

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

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

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

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

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

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

1
if (count > result) result = count;

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

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

贪心代码:

自己写的错误代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    int maxSubArray(vector<int> &nums) {
        // 贪心思路
        int ret = INT_MIN;
        int n = nums.size();
        int count = 0; //
        for (int i = 0; i < n; i++) {
            count += nums[i];
            if (count < 0) {
                count = 0;
            }
            if (ret < count) {
                ret = count;
            }
        }
        return ret;
    }
};

错误原因如下.加上当前的nums[i]之后,应该先计算ret,然后判断加上当前的nums[i]之后的count与0的大小,然后判断要不要更新起始位置.

例如输入nums = [-1], 错误代码的输出就是0, 但是正确的预期结果却是-1

正确代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    int maxSubArray(vector<int> &nums) {
        // 贪心思路
        int ret = INT_MIN;
        int count = 0;
        int n = nums.size();
        for (int i = 0; i < n; i++) {
            count += nums[i];
            if (ret < count) {
                ret = count;
            }
            if (count < 0) {
                count = 0;
            }
        }
        return ret;
    }
};

常见误区

误区一：

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

误区二：

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

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

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

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

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

误区三:

也就是自己犯的错误.应该先更新ret, 再更新区间起始位置.因为ret完全有可能是负数, 当数组的元素都是负数的时候ret就一定是负数.

待更新……