贪心算法

读前福利，送大家一些电子书

全文概览

理论基础

贪心算法，又名贪婪法，是寻找最优解问题的常用方法，也是互联网大厂在面试过程中经常要考察的算法思想。贪心算法有非常多的经典应用，比如我们熟知的霍夫曼编码（Huffman Coding）、普里姆算法（Prim） 、克鲁斯卡尔算法（Kruskal） 和 迪杰斯特拉算法（Dijkstra) 等等。

贪心算法基本思想

贪心算法是指，在对问题进行求解时，总是做出目前看起来最好的选择。简单来说，就是选择每一阶段的局部最优，从而期望达到全局最优。

什么时候用贪心

贪心算法没有固定的算法框架，这也导致我们在平时做题的过程中很不容易想到能否用贪心来求解，所以我们只能多多练习。

要确定一个问题是否能用贪心算法来求解，我们必须证明每一步所做的贪心选择能够保证问题取得全局最优解。一般证明的方式有两种，即数学归纳法和反证法。具体的证明过程，如果大家感兴趣可以去查阅相关资料，这里就不再赘述。

其实，我们在平时做题的过程中，如果遇到求解最优解问题时。如果我们感觉可以通过局部最优推导出全局最优，而且又想不到反例来推翻自己的结论，那么就不妨试一试贪心法，然后跑一跑测试用例，如果不通过，那我们再换动态规划等方法求解就好了。

简单来说，利用贪心法求解的问题一般具备如下2个特征。

• 贪心选择性质

一个问题的整体最优解可通过一系列局部的最优解的选择达到，并且每次的选择可以依赖以前作出的选择，但不依赖于后面要作出的选择（也称为无后效性）。

• 最优子结构性质

当一个问题的最优解包含其子问题的最优解时，则称此问题具有最优子结构性质。问题的最优子结构性质是该问题可用贪心法求解的关键所在。

贪心算法解题步骤

理论过于抽象，下面我们通过经典的背包问题为例来感受一下贪心算法的解题思路。

假设我们有一个可以容纳 10kg 物品的背包，可以装各种物品。我们有以下 5 物品，每种物品的总量和总价值都各不相同。为了让背包中所装物品的总价值最大，我们如何选择在背包中装哪些物品？每种物品又该装多少呢？

也许你一下子就能想到该问题的求解思路，就是先算一下所有物品的单价，然后按照单价由高到低来装就好了。题目中物品单价从高到低依次是：榴莲、苹果、橙子、梨、香蕉，所以，我们可以往背包里装5kg的榴莲，3kg的苹果，2kg的橙子。

这个问题的求解思路本质上就是借助了贪心法求解。下面我们结合这个例子来看一下贪心算法的解题步骤。

1. 对于求解如下问题时，首先要联想到贪心算法

   给定一组数据，我们从中选出一些数据，使得满足限制条件的前提下，期望值取得最大。以给定的例子为例，限制条件就是背包能装下的重量10kg，期望值就是物品的总价值。

2. 尝试看一下这个问题是否能用贪心法来求解

   每次选择当前情况下，在对限制值同等贡献量的情况下，对期望值贡献最大的数据。以给定的例子为例，我们从剩下的物品里面，选择单价最高的。

3. 我们举几个例子来验证一下贪心算法产生的结果是否是最优的。

   要想严格的证明贪心算法的正确性，是非常复杂的，需要用到比较多的数学推理。我们一般在做题的过程中，举几个例子验证一下就可以了，然后跑一下测试用例验证一下。

跳跃游戏

55. 跳跃游戏

问题描述

给定一个非负整数数组 nums ，你最初位于数组的 第一个下标 。数组中的每个元素代表你在该位置可以跳跃的最大长度。判断你是否能够到达最后一个下标。

示例

输入：nums = [2, 3, 1, 1, 4]

输出：true

解释：可以先跳 1 步，从下标 0 到达下标 1, 然后再从下标 1 跳 3 步到达最后一个下标。

分析问题

这道题是判断能否到达最后一个下标，换句话说，就是最远能跳到的位置是否大于等于数组的最后一个下标（如果能到达某个位置，那一定能到达它前面的所有位置）。

我们可以使用贪心法来求解。还记得我们的贪心算法的求解步骤吗？我们这里直接套模板~

1. 对于求解如下问题时，首先要联想到贪心算法

   给定一组数据，我们从中选出一些数据，使得满足限制条件的前提下，期望值取得最大。以给定的例子为例，没有限制条件，期望值就是最远能跳到的位置。

2. 尝试看一下这个问题是否能用贪心法来求解

   每次选择当前情况下，在对限制值同等贡献量的情况下，对期望值贡献最大的数据。以给定的例子为例，在每走一步的过程中，尽可能到达的最远位置（贪心，局部最优）。

3. 我们举几个例子来验证一下贪心算法产生的结果是否是最优的。

   我们这里也举不出反例，所以我们不妨来用贪心求解试试。

下面我们直接看代码实现。

class Solution:
    def canJump(self, nums):
        n=len(nums) #数组的长度
        max_num=0 #初始化最远可以到达的位置
        #遍历数组中的每一个位置
        for i in range(n):
            #如果该位置在最远可以到达的位置的范围内
            if i <= max_num:
                #更新最远可以到达的位置
                max_num = max(max_num, i + nums[i])
                #如果最远可以到达的位置大于数组的最后一个位置的下标，则返回True
                if max_num >= n - 1:
                    return True
        return False

该算法的时间复杂度是O(n)，空间复杂度是O(1)。

跳跃游戏II

45. 跳跃游戏 II

问题描述

给你一个非负整数数组 nums ，你最初位于数组的第一个位置。数组中的每个元素代表你在该位置可以跳跃的最大长度。你的目标是使用最少的跳跃次数到达数组的最后一个位置。假设你总是可以到达数组的最后一个位置。

示例：

输入：nums = [2, 3, 1, 1, 4]

输出：2

解释：跳到最后一个位置的最小跳跃数是 2。从下标为 0 跳到下标为 1 的位置，跳 1 步，然后跳 3 步到达数组的最后一个位置。

分析问题

这道题是上一题的升级版本，我们一样可以采用贪心算法来求解，在每走一步的过程中，寻找尽可能到达的最远位置（局部最优）。

例如对于数组 nums = [2, 3, 1, 1, 4] ，初始位置是下标 0，从下标 0 出发，最远可到达下标 2，即可跳的范围如下图所示的粉色节点。因为此时下标 1 的值是 3，从下标 1 出发可以达到更远的位置，所以第一步到达下标 1。

在具体的实现中，我们维护当前能够到达的最大下标位置，记为边界。我们从左到右遍历数组，到达边界时，更新边界并将跳跃次数增加 1。

这里有一个小的细节需要注意，在遍历数组时，我们不访问最后一个元素，这是因为在访问最后一个元素之前，我们的边界一定大于等于最后一个位置，否则就无法跳到最后一个位置了。如果访问最后一个元素，在边界正好为最后一个位置的情况下，我们会增加一次「不必要的跳跃次数」，因此我们不必访问最后一个元素。

下面我们来看一下代码的实现。

class Solution:
    def jump(self, nums):
        n = len(nums)
        #代表边界位置
        end = 0
        #最远可以到达的位置
        max_num=0
        step=0
        for i in range(n - 1):
            if max_num >= i:
                max_num = max(max_num, i + nums[i])
                if i == end:
                    end = max_num
                    step += 1
        return step

该算法的时间复杂度是O(n)，空间复杂度是O(1)。

加油站

问题描述

在一条环路上有 N 个加油站，其中第 i 个加油站有汽油 gas[i] 升。

你有一辆油箱容量无限的的汽车，从第 i 个加油站开往第 i+1 个加油站需要消耗汽油 cost[i] 升。你从其中的一个加油站出发，开始时油箱为空。如果你可以绕环路行驶一周，则返回出发时加油站的编号，否则返回 -1。

说明:

• 如果题目有解，该答案即为唯一答案。
• 输入数组均为非空数组，且长度相同。
• 输入数组中的元素均为非负数。

示例：

输入：gas = [1,2,3,4,5]，cost = [3,4,5,1,2]

输出：3

解释：从 3 号加油站（索引为 3 处）出发，可获得 4 升汽油。此时油箱有 = 0 + 4 = 4 升汽油
开往 4 号加油站，此时油箱有 4 - 1 + 5 = 8 升汽油
开往 0 号加油站，此时油箱有 8 - 2 + 1 = 7 升汽油
开往 1 号加油站，此时油箱有 7 - 3 + 2 = 6 升汽油
开往 2 号加油站，此时油箱有 6 - 4 + 3 = 5 升汽油
开往 3 号加油站，你需要消耗 5 升汽油，正好足够你返回到 3 号加油站。
因此，3 可为起始索引。

分析问题

我们可以把题目的描述抽象成如下的图形结构。其中节点代表每个加油站（节点的值表示可以添加的油量），边的值表示从一个点到另外一个点需要消耗的油量。

这道题最容易想到的就是暴力求解，即遍历所有的站点，以其为出发点，看是否能转一圈再回来。该算法使用了两层for循环，其算法的时间复杂度是O(N^2)。

class Solution:
    def canCompleteCircuit(self, gas, cost):
        #站点个数
        n=len(gas)
        #遍历所有站点，以其为出发点
        for start in range(n):
            j = start
            remain = gas[start]
            #判断当前剩余的油能否到达下一个点
            while remain - cost[j] >= 0:
                #更新剩余的油量
                remain = remain - cost[j] + gas[(j + 1) % n]
                #顺时针移动一位
                j = (j + 1) % n
                #当回到了起始点，代表可以走完一圈，直接返回
                if j == start:
                    return start
        return -1

下面我们来看一下如何进行优化。

优化

在汽车进入加油站站点 i 时，可以加 gas[i] 的油，当离开站点 i ，走到下一个站点 i+1 时， 需要消耗 cost[i] 的油，那么我们可以把站点和与其相连的路看做一个整体来考虑，即 gas[i] - cost[i] 作为经过站点 i 的 油的变化量。如下图所示：

这样，我们就生成了一个环形数组，数组中的第 i 个元素就是 gas[i] - cost[i]。

通过转换后，我们就可以把题目要求变成判断这个环形数组中是否能够找到一个起点start，使得从这个起点开始的累加和一直大于等于 0。

在计算累加和的过程中，如果累加和小于0，就代表以该加油站为起点，是不能走完一圈的，需要换一个加油站作为起点。

决定换哪个加油站为起点呢？这是本题优化的关键所在，也是使用贪心思路求解的关键结论。

这个结论就是：如果选择加油站i作为起点「恰好」无法走到加油站j，那么加油站 i和j中间的任意站点k都不可能作为起点。

下面我们试着来证明一下这个结论的正确性。

假设 sum 记录的是当前油箱的剩余油量，如果从加油站 i （sum=0）出发，走到加油站 j 恰好出现 sum < 0 的情况，也就是说从站点 i 走到 站点k（站点 k 位于 站点 i 和 j 之间）都满足 sum > 0 。

如果把 k 作为起点的话，相当于在站点 k 时， sum=0（出发时，油箱的油量为0），则走到站点 j 时 必然有 sum < 0，也就说明 k 肯定不能是起点。

综上，这个结论就被证明了。

所以，如果我们发现从站点 i 出发无法走到站点 j ，那么站点i以及i, j之间的所有站点都不可能作为起点，从而我们可以减少一些冗余计算了。

具体代码如下所示：

class Solution:
    def canCompleteCircuit(self, gas, cost):
        #站点个数
        n=len(gas)
        #邮箱的剩余量
        sum=0
        #出发位置
        start=0
        while start < n:
            step=0
            while step<n:
                j = (start+step) % n
                # 计算累加和
                sum += gas[j] - cost[j]
                # 如果累加和小于0，
                # 代表以start为起点不能走完一圈
                if sum<0:
                    break

                step=step+1

            if step==n:
                #如果已经走完一圈，直接返回start
                return start
            else:
                #更新start
                start=start+step+1
                sum=0

        return -1

分糖果

575. 分糖果

问题描述

给定一个偶数长度的整数数组，数组中不同的数字代表着不同种类的糖果。每个数字代表一个糖果，现在你需要把这些糖果平均分配给一个弟弟和一个妹妹，返回妹妹可以获得的最大的糖果的种类数。

示例：

输入: candies = [2,2,3,3,4,4]

输出: 3

解析: 数组中有三种不同的数字2、3、4，代表了三种不同种类的糖果，每一种都有两个。在这种情况下，最优的分配方案是，妹妹获得[2,3,4]，弟弟也获得[2,3,4]。这样使得妹妹获得的糖果种类数最多。

分析问题

根据题目要求，需要平均分配糖果给弟弟和妹妹，所以妹妹能分配到的糖果数量为n/2。最好的情况是妹妹得到的n/2个糖果是属于不同种类的，也就是说妹妹可以得到的最大的糖果种类数是n/2。此外，如果数组中糖果的种类数小于n/2时，为了使妹妹得到的糖果种类数达到最大，我们会将数组中不同种类的糖果分配给妹妹。因此，在这种情况下，妹妹能获得的不同种类的糖果数量等于给定数组中糖果的种类数。

现在我们就把问题转化成如何求出数组中糖果的种类数，假设为count。那么分配给妹妹的最大糖果种类数就是min(n/2,count)。下面我们来看一下如何求出数组中糖果的种类数，最直观的想法就是遍历给定的数组，然后将元素放入一个集合Set中，利用集合Set能去重的特性，来求出数组的糖果的种类的个数。

def distributeCandies(candies):
    candies_set=set()
    #遍历数组
    for canday in candies:
        #为了获得不同种类的糖果数
        candies_set.add(canday)
        
    return min(len(candies)/2, len(candies_set))

candies = [1,1,2,2,3,3]
print(distributeCandies(candies))

分糖果II

1103. 分糖果 II

问题描述

我们现在有candies个糖果，打算把他们分配给排好队的n个小朋友。我们采取下面这种分配策略。给第一个小朋友1颗糖果，第二个小朋友2颗，依此类推，直到给最后一个小朋友n颗糖果。然后，我们再回到队伍的起点，给第一个小朋友n + 1颗糖果，第二个小朋友n + 2颗，依此类推，直到给最后一个小朋友2 * n颗糖果。重复上述过程（每次都比上一次多给出一颗糖果，当到达队伍终点后再次从队伍起点开始），直到我们分完所有的糖果。注意，就算我们手中的剩下糖果数不够（不比前一次发出的糖果多），这些糖果也会全部发给当前的小朋友。返回一个长度为n、元素之和为candies的数组，以表示糖果的最终分发情况（即 ans[i] 表示第 i 个小朋友分到的糖果数）。

示例：

输入：candies = 9, n= 3

输出：

解释：
第一次，ans[0] += 1，数组变为 [1,0,0,0]。
第二次，ans[1] += 2，数组变为 [1,2,0,0]。
第三次，ans[2] += 3，数组变为 [1,2,3,0]。
第四次，ans[3] += 3（因为此时只剩下 3 颗糖果），最终数组变为 [1,2,3,3]。

分析问题

拿到这个问题最直观的想法就是不断的把糖果分配给n个小朋友，直到把糖果分配完为止。下面我们来看一下代码如何实现。

def distributeCandies(candies,n):
    ans=[0]*n
    i=0

    while candies>0:
        #分配给哪个人了
        index=i%n
        ans[index]=ans[index]+min(i+1,candies)
        candies=candies-min(i+1,candies)
        i=i+1

    return ans

candies=9
n=4
print(distributeCandies(candies,n))

分糖果III

135. 分发糖果

问题描述

现在有一群孩子做游戏，请你根据游戏得分来发糖果，要求如下：

1. 每个孩子不管得分多少，起码分到一个糖果。

2. 任意两个相邻的孩子之间，得分较多的孩子必须拿多一些糖果。(若相同则无此限制)

给定一个数组arr代表得分数组，那你根据规则分配糖果最少需要多少颗呢？

分析问题

首先，我们可以把题目的第二条规则拆分来看一下。对于任意相邻的孩子之间，我们可以拆分为左孩子和右孩子。

1. 左规则：当左孩子ratings[i-1]<ratings[i]时，当前孩子i的糖果数量要比它的左孩子i-1的多。
2. 右规则：当右孩子ratings[i+1]<ratings[i]时，当前孩子i的糖果数量要比它的右孩子i+1的多。

我们通过遍历两遍数组，分别求出每个孩子在满足左规则和右规则时，最少需要的糖果数量left、right。那么每个孩子最终分得的糖果数量就为这两个值left、right的最大值，即max(left,right)。下面我们来看一下代码实现。

def candy_count(ratings):
        n = len(ratings)
        # 用来保存满足左规则所需要的最少的糖果数
        left = [1] * n

        for i in range(1, n):
            if ratings[i] > ratings[i - 1]:
                left[i] = left[i - 1] + 1


        right = result = max(left[n-1],1)
        for i in range(n - 2, -1, -1):
            if ratings[i] > ratings[i + 1]:
                right += 1
            else:
                right = 1
            result += max(left[i], right)

        return result

s=[1,3,5,3,2,1]
print(candy_count(s))

我们来看一下算法的复杂度。

1. 时间复杂度：O(n)，其中n个孩子的数量。我们需要遍历两遍数组来求出满足规则所需要的最少糖果数。
2. 空间复杂度：O(n)。

那我们有什么方法可以来降低空间复杂度吗？

优化

根据题目要求，我们在分配糖果时要尽量少分配，并且每个孩子起码要分配到1个糖果。

我们从左到右遍历每一个同学，记前一个同学分得的糖果数量为pre。

1. 如果当前同学比上一个同学的得分要高，说明我们目前处于最近的递增序列中，所以需要给该同学分配pre+1个糖果。
2. 如果当前同学和上一个同学的得分相同，我们就给一个糖果，这样不违反规则。
3. 如果当前同学比上一个同学的得分要低，我们就给当前同学分配一个糖果。同时，为了保证分配的糖果数量还满足条件，我们需要给该同学所在的递减序列中的其它同学再分配一个糖果（这里可能不太好理解，我们通过一个例子来说明），所以我们需要一个变量dec来记录递减序列的长度。这里有一点需要注意，当递减序列长度和上一个递增序列长度相同时，我们需要把最近的递增序列的最后一个同学并入到递减序列中。

我们来具体分析一个例子。假设有5个孩子，它们的得分别是1、3、5、3、2、1。







下面我们来看一下代码如何实现。

def candy_count(ratings):
    n = len(ratings)
    ret = 1
    #递增序列长度
    inc = 1
    #递减序列长度
    dec = 0
    #前一个孩子的糖果数
    pre = 1

    for i in range(1, n):
        if ratings[i] >ratings[i - 1]:
            dec = 0
            pre = pre + 1
            ret = ret + pre
            inc = pre
        elif ratings[i] == ratings[i-1]:
            dec = 0
            pre = 1
            ret = ret + pre
            inc = 1
        else:
            dec += 1
            if dec == inc:
                dec += 1
            ret += dec
            pre = 1

    return ret

s=[1,3,5,3,2,1]
print(candy_count(s))

我们来看一下算法的复杂度。

1. 时间复杂度：O(n)。
2. 空间复杂度：O(1)。

合并区间

问题描述

56. 合并区间

以数组 intervals 表示若干个区间的集合，其中单个区间为 intervals[i] = [start_i, end_i] 。请你合并所有重叠的区间，并返回一个不重叠的区间数组，该数组需恰好覆盖输入中的所有区间。

输入：intervals = [ [1，3]，[2，6]，[8，10]，[15，18] ]
输出：[ [1，6]，[8，10]，[15，18] ]
解释：区间 [1，3] 和 [2，6] 重叠，将它们合并为 [1，6]

分析问题

对于任意两个区间A和B，它们之间的关系可以有以下6种情况。

我们将这两个区间进行比较、交换，使得第一个区间的起始位置 ≤ 第二个区间的起始位置这个条件成立，这样的话，我们就可以把这6种情况转换成以下3种。

按照这个思路，我们将所有区间按照左端点进行排序，那么就可以保证任意连续的两个区间，第一个区间的起始位置 ≤ 第二个区间的起始位置，所以他们的关系只有上面三种情况。

算法

对于上面的三种情况，我们可以采用如下算法来求解。

首先，我们用数组 merged 存储最终的答案。然后我们将第一个区间加入 merged 数组中，并按顺序依次考虑之后的每个区间：

• 如果当前区间的左端点在数组 merged 中最后一个区间的右端点之后，即上图中的第二种情况，那么它们不会重合。我们可以直接将这个区间加入数组 merged 的末尾；

• 否则，它们是有重合部分的，即上图中的第一、三种情况，我们需要用当前区间的右端点更新数组 merged 中最后一个区间的右端点，将其置为二者的较大值。

这样，我们就可以解决上述的三种情况，下面我们来看一下代码的实现。

class Solution:
    def merge(self, intervals):
        #将区间数组按照左端点进行升序排序
        intervals.sort(key=lambda x: x[0])
        #存放合并后的结果
        merged = []
        for interval in intervals:
            #如果列表为空
            #或者当前区间的左端点大于merged最后一个元素的右端点，直接添加
            if not merged or merged[-1][1] < interval[0]:
                merged.append(interval)
            else:
                #否则的话，我们就可以与上一区间进行合并
                #修改merged最后一个元素的右端点为两者的最大值
                merged[-1][1] = max(merged[-1][1], interval[1])
        return merged

该算法的时间复杂度是O(nlogn)，其中n是区间的数量，除去排序的开销，我们只需要一次线性扫描，所以主要的时间开销是排序的 O*(*n logn)。

空间复杂度是O(logn)。