CodeAshen's blog
CodeAshen
2023-02-10
目录

09-贪心算法

# 贪心基础（分发饼干）

# 问题分析

贪心算法通常是实现起来非常简单的一类算法，通常贪心算法的代码会非常短，而且思路也非常简单，贪心算法真正的难点在于确定当前问题可以使用贪心算法。下面先来看一个简单的贪心算法问题。

455. 分发饼干 (opens new window)

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

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

在本题中，为了尽可能让更多的孩子满足，可以尝试将最大的饼干给胃口最大的孩子，如果最大的饼干可以满足胃口最大的孩子，我们留给下一个胃口次大的孩子的饼干也将是当前看来最大的饼干，相当于我们对饼干留了一个富裕。另一方面，如果最大的饼干都无法满足胃口最大的孩子，那所有的饼干都不能满足他，这种情况只能尝试让最大的饼干满足胃口次大的孩子。这样的每次都尝试当前剩下的最大的饼干满足胃口最大的孩子，能最大程度保证最多的孩子满足。

根据这样的思路，实现起来也并不难，不过实现这样一个算法必须要将饼干大小数组和孩子胃口值数组排序。其实贪心算法永远牵扯到我们每一次都要取最大值或者最小值这样的操作，所以通常实现贪心算法和排序是分不开的。所以如果题目没有说数组是有序的，我们就要先进行排序。

# 代码实现

  1. 尝试先满足最胃口值最大的孩子

    /**
 * 先尝试满足最胃口大的孩子
 * 时间复杂度: O(nlogn)
 * 空间复杂度: O(1)
 *
 * @param g 胃口值数组
 * @param s 饼干数组
 * @return 返回最多满足孩子数
 */
public int findContentChildren1(int[] g, int[] s) {
    // 胃口值和饼干大小排序
    Arrays.sort(g);
    Arrays.sort(s);

    // gi、si 分别指向最大胃口值和最大饼干
    int gi = g.length - 1;
    int si = s.length - 1;

    int res = 0;  // 已经满足的孩子数量
    while (gi >= 0 && si >= 0) {
        if (s[si] >= g[gi]) {
            // 如果饼干可以满足当前孩子，res 加一，继续考察下一个饼干和孩子
            res++;
            gi--;
            si--;
        } else {
            // 如果没法满足，则所有的饼干都没法满足，跳过这个孩子
            gi--;
        }
    }

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

  2. 尝试先满足最胃口值最小的孩子

    /**
 * 先尝试满足最胃口小的孩子
 * 时间复杂度: O(nlogn)
 * 空间复杂度: O(1)
 *
 * @param g 胃口值数组
 * @param s 饼干数组
 * @return 返回最多满足孩子数
 */
public int findContentChildren2(int[] g, int[] s) {
    // 胃口值和饼干大小排序
    Arrays.sort(g);
    Arrays.sort(s);

    // gi、si 分别指向最大胃口值和最大饼干
    int gi = 0;
    int si = 0;

    int res = 0;  // 已经满足的孩子数量
    while (gi < g.length && si < s.length) {
        if (s[si] >= g[gi]) {
            // 如果饼干可以满足当前孩子，res 加一，继续考察下一个饼干和孩子
            res++;
            gi++;
            si++;
        } else {
            // 如果没法满足，则这块饼干没法满足任何孩子，跳过这块饼干
            si++;
        }
    }

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

# 相关问题

392. 判断子序列 (opens new window)

给定字符串 s 和 t ，判断 s 是否为 t 的子序列。字符串的一个子序列是原始字符串删除一些（也可以不删除）字符而不改变剩余字符相对位置形成的新字符串。（例如，"ace"是"abcde"的一个子序列，而"aec"不是）。

# 贪心算法与动态规划的关系（无重叠区间）

# 问题描述

贪心算法和动态规划看似不相干，其实有着挺密切的关系，这一节我们通过一个问题看看贪心算法和动态规划的关系。

435. 无重叠区间 (opens new window)

给定一个区间的集合，找到需要移除区间的最小数量，使剩余区间互不重叠。

注意:

  • 可以认为区间的终点总是大于它的起点。
  • 区间 [1,2] 和 [2,3] 的边界相互“接触”，但没有相互重叠。

（1）动态规划分析

这个问题问的是最少删除多少个区间，我们可以将问题看作是最多保留多少个区间，使得这些区间互相不重叠。还是一样，当我们没有思路的时候不妨先想想暴力解法如何解决。

暴力解法：找出所有子区间的组合，之后判断它不重叠。时间复杂度是 O((2^n)*n)，其中 2^n 是指对于每一个区间都可以选择留下或者不留下，这样给给定了一组 n 个区间的话，就有 2^n 种组合，最后有 O(n) 的时间复杂度判断是否重叠。

先要对区间排序，才能方便判断是否有重叠。对于区间来说，通常按照起始点进行排序。

经过上面分析我们发现这又是一个组合问题，对于组合问题我们可以思考是否可以使用动态规划来解决。我们对这些区间排好序之后现在在这些区间中保留对多的区间使得他们互相不重叠，这件事像极了最长上升子序列，我们每次对每个区间 i 都可以回头看它前面的所有区间，看是否可以跟在前面某个区间的后面，如果可以，前面区间的最大不重叠区间数加 1，就是包含区间 i 的不重叠区间数。在这些可以接上的所有的不重叠区间数中取出最大的加 1 就是以区间 i 结尾的最大不重叠区间数。

（2）贪心算法分析

每次选择中，每个区间的右边界很重要，右边界越小，留给后面区间的空间越大，后面越有可能容纳更多的区间。依据这样的思考，可以设计下面的贪心算法。

按照区间的右边界排序从小到大排序，每次都选择有边界最小的且和前一个区间不重叠的区间跟在后面，这样以此类推，就设计出了一个贪心算法。

# 代码实现

  1. 动态规划**（leetcode 超时， O(n^2) ）**

    /**
 * 动态规划
 * 时间复杂度: O(n^2)，提交到 leetcode 超时
 * 空间复杂度: O(n)
 */
class Solution {
    /**
     * 动态规划解法，借鉴最长递增子序列的思路，求出最大不重叠区间数 res，
     * 然后用总区间数 length - res 就是最少移除区间数
     *
     * @param intervals intervals[i][0] 表示第 i 个区间左边界，intervals[i][1] 表示第 i 个区间右边界，二维索引只有 0，1
     * @return 最少移除区间数量，使得剩余区间不重叠
     */
    public int eraseOverlapIntervals(int[][] intervals) {
        if (intervals.length == 0) {
            return 0;
        }

        Arrays.sort(intervals, (o1, o2) -> {
            if (o1[0] != o2[0]) {
                return o1[0] - o2[0];   // 优先比较区间左边界
            } else {
                return o1[1] - o2[1];   // 左边界相同比较有边界
            }
        });

        // memo[i] 表示以 intervals[i] 结尾的区间能构成的最长不重叠区间序列数
        int[] memo = new int[intervals.length];
        Arrays.fill(memo, 1);
        for (int i = 1; i < intervals.length; i++) {  // 外层循环考察 0 号区间之后的每个区间
            for (int j = 0; j < i; j++) {  // 内层循环考察 区间 i 之前的所有区间
                if (intervals[i][0] >= intervals[j][1]) {  // 不重叠
                    memo[i] = Math.max(memo[i], 1 + memo[j]);
                }
            }
        }

        // 找到最长不重叠区间数
        int res = 0;
        for (int item : memo) {
            res = Math.max(res, item);
        }

        return intervals.length - res;  // 求的是最少移除区间数量
    }
}
    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
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46

  2. 贪心算法

    /**
 * 贪心算法
 * 时间复杂度: O(n)
 * 空间复杂度: O(n)
 */
class Solution {
    /**
     * 贪心算法求解
     *
     * @param intervals intervals[i][0] 表示第 i 个区间左边界，intervals[i][1] 表示第 i 个区间右边界，二维索引只有 0，1
     * @return 最少移除区间数量，使得剩余区间不重叠
     */
    public int eraseOverlapIntervals(int[][] intervals) {
        if (intervals.length == 0) {
            return 0;
        }

        Arrays.sort(intervals, (o1, o2) -> {
            if (o1[1] != o2[1]) {
                return o1[1] - o2[1];   // 按照右边界从小到大排序
            } else {
                return o1[0] - o2[0];   // 右边界相同，按左边界从小到大
            }
        });

        int res = 1;  // 最长不重叠子区间序列数量
        int pre = 0;  // 当前得到最长不重叠子区间序列的末尾区间索引，即 intervals[pre] 是当前序列的最后一个
        for (int i = 1; i < intervals.length; i++) {
            if (intervals[i][0] >= intervals[pre][1]) {
                res++;
                pre = i;
            }
        }

        return intervals.length - res;  // 求的是最少移除区间数量
    }
}
    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
    37

# 贪心选择性质证明

# 贪心选择性质

上一节我们看到有些动态规划的问题是可以用贪心算法解决的，这类问题都满足贪心选择性质。

贪心选择性质：在求解一个最优化的问题中，使用贪心的方式选择了一组内容之后，不会影响剩下的子问题的的求解。

这个性质说起来比较简单，但是验证一个问题是否满足贪心选择性质是比较难的。通常一个问题如果我们想用贪心算法的话，我们要多举例验证。同样如果无法使用贪心算法，举出反例即可，在研究动态规划中的背包问题时，我们就介绍过不能使用贪心算法放入单位价值最高的物品。

再来看一个不能使用贪心算法的反例：

279. 完全平方数 (opens new window)

给定正整数 n，找到若干个完全平方数（比如 1, 4, 9, 16, ...）使得它们的和等于 n。你需要让组成和的完全平方数的个数最少。

给你一个整数 n ，返回和为 n 的完全平方数的 最少数量 。

完全平方数 是一个整数，其值等于另一个整数的平方；换句话说，其值等于一个整数自乘的积。例如，1、4、9 和 16 都是完全平方数，而 3 和 11 不是。

直觉是能不能使用贪心算法，优先使用小于等于 n 的最大的完全平方数，一直加到等于 n 为止。其实是不行的，反例是

  • 12 = 9 + 1 + 1 + 1，优先使用最大的完全平方数，最后用了 4 个完全平方数
  • 12 = 4 + 4 + 4，正确答案是 3 个完全平方数

这样一个反例就能得出贪心选择性质不成立。

但是对于很多算法可能举不出反例，如何证明贪心选择的正确性呢？在算法设计领域，如果遇到类需要证明的问题，通常首先想到使用数学归纳法和反证法。

# TODO 使用反证法证明区间问题满足贪心选择性质

编辑 (opens new window)
上次更新: 2023/06/04, 12:34:19
08-动态规划

←

最近更新
01
第01章-RabbitMQ导学
02-10
02
第02章-入门RabbitMQ核心概念
02-10
03
第03章-RabbitMQ高级特性
02-10
更多文章>
Theme by Vdoing | Copyright © 2020-2023 CodeAshen | MIT License