贪心算法套路框架

AI summary

type

status

date

slug

summary

贪心选择性质

我们稍微改一改上面的题目：

现在有两种钞票，面额分别为 1 元和 100 元，每种钞票的数量无限。现在给你一个目标金额 amount，请问你最少需要多少张钞票才能凑出这个金额？

问题二和问题一到底有什么区别？区别在于，前者没有贪心选择性质，而后者有。

贪心选择性质就是说能够通过局部最优解直接推导出全局最优解。

结合案例来说，对于问题一，局部最优解就是每次都选择 100 元，因为 100 > 1；对于问题二，局部最优解也是每次都选择 100 元，因为每张面额尽可能大，所需的钞票数量就能尽可能少。

但区别在于，问题一中每一次选择的局部最优解组合起来就是全局最优解，而问题二中不是。

比方说目标金额 amount = 3，虽然每次选择 100 元是局部最优解，但想凑出 3 元，只能选择 3 张 1 元，局部最优解不一定能构成全局最优解。

对于问题二的场景，不符合贪心选择性质，所以不能用贪心算法，只能穷举所有可行解，才能计算出最优解。

💡

贪心选择性质 vs 最优子结构

动态规划解题套路框架 中提到，算法问题必须要有「最优子结构」性质，才能通过子问题的最优解推导出全局最优解，这是动态规划算法的基础。

那么就有读者搞不清楚了，这个「贪心选择性质」和「最优子结构」有什么区别？

最优子结构的意思是说，现在我已经把所有子问题的最优解都求出来了，然后我可以基于这些子问题的最优解推导出原问题的最优解。

贪心选择性质的意思是说，我只需要进行一些局部最优的选择策略，就能直接知道哪个子问题的解是最优的了，且这个局部最优解可以推导出原问题的最优解。此时此刻我就能知道，不需要等到所有子问题的解算出来才知道。

所以贪心算法的效率一般都比较高，因为它不需要遍历完整的解空间。

跳跃游戏

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

注意题目说 nums[i] 表示可以跳跃的最大长度，不是固定长度。假设 nums[i] = 3，意味着你可以在索引 i 往前跳 1 步、2 步或 3 步。

我们先思考暴力穷举解法吧，如何穷举所有可能的跳跃路径？你心里的那棵多叉树画出来了没有？

假设 N 为 nums 的长度，这道题相当于做 N 次选择，每次选择有 nums[i] 种选项，想要穷举所有的跳跃路径，就是一棵高度为 N 的多叉树，每个节点有 nums[i] 个子节点。

这个算法本质上还是穷举了所有可能的选择，可以走动态规划那一套流程进行优化，但是这里我们先不急，可以再仔细想想，这个问题有没有贪心选择性质？

比方说你现在站在 nums[i] = 3 的位置，你可以跳到 i+1, i+2, i+3 三个位置，此时你真的需要分别跳过去，然后递归求解子问题 dp(i+1), dp(i+2), dp(i+3)，最后通过子问题的答案来决定 dp(i) 的结果吗？

其实不用的，只用维护一个能到达的最远距离即可。具体看代码：

跳跃游戏 Ⅱ

给定一个长度为 n 的 0 索引整数数组 nums。初始位置为 nums[0]。
每个元素 nums[i] 表示从索引 i 向前跳转的最大长度。换句话说，如果你在 nums[i] 处，你可以跳转到任意 nums[i + j] 处:
0 <= j <= nums[i]
i + j < n
返回到达 nums[n - 1] 的最小跳跃次数。生成的测试用例可以到达 nums[n - 1]。

上图这种情况，我们站在索引 0 的位置，可以向前跳 1，2 或 3 步，你说应该选择跳多少呢？

你可以确定地说，应该跳 2 步调到索引 2，因为 nums[2] 的可跳跃区域涵盖了索引区间 [3..6]，比其他的都大。题目求最少的跳跃次数，那么往索引 2 跳必然是最优的选择。

(可以反证一下，假设跳到 3 更好，那么就说明 3 能跳到一个更好的位置，但是已知 2 能跳的范围比 3 大，所以 3 能跳到的地方 2 一定也能跳到，那么选 2 也不影响得到最优解。

这就是贪心选择性质，我们不需要真的递归穷举出所有选择的具体结果来比较求最值，而只需要每次选择那个最有潜力的局部最优解，最终就能得到全局最优解。

贪心算法的关键在于问题是否具备贪心选择性质，所以只能具体问题具体分析，没办法抽象出一套固定的算法模板或者思维模式，判断一道题是否是贪心算法。

我的经验是，没必要刻意地识别一道题是否具备贪心选择性质。你只需时刻记住，算法的本质是穷举，遇到任何题目都要先想暴力穷举思路，穷举的过程中如果存在冗余计算，就用备忘录优化掉。

如果提交结果还是超时，那就说明不需要穷举所有的解空间就能求出最优解，这种情况下肯定需要用到贪心算法。你可以仔细观察题目，是否可以提前排除掉一些不合理的选择，是否可以直接通过局部最优解推导全局最优解。

加油站

在一条环路上有 n 个加油站，其中第 i 个加油站有汽油 gas[i] 升。
你有一辆油箱容量无限的的汽车，从第 i 个加油站开往第 i+1 个加油站需要消耗汽油 cost[i] 升。你从其中的一个加油站出发，开始时油箱为空。
给定两个整数数组 gas 和 cost ，如果你可以按顺序绕环路行驶一周，则返回出发时加油站的编号，否则返回 -1 。如果存在解，则保证它是唯一的。

「图像解法」

汽车进入站点 i 可以加 gas[i] 的油（图中绿色数字），离开站点会损耗 cost[i] 的油（图中红色数字），那么可以把站点和与其相连的路看做一个整体，将 gas[i] - cost[i] 作为经过站点 i 的油量变化值。

这样，题目描述的场景就被抽象成了一个环形数组，数组中的第 i 个元素就是 gas[i] - cost[i]。

有了这个环形数组，我们需要判断这个环形数组中是否能够找到一个起点 start，使得从这个起点开始的累加和一直大于等于 0。

如下图所示：

那么你是否能根据这幅图，判断把哪一个加油站作为起点呢？

显然，将 0 作为起点肯定是不行的，因为 sum 在变化的过程中小于 0 了，不符合我们「累加和一直大于等于 0」的要求。

看图说话，显然图像的最低点最有可能可以作为起点。如果把这个「最低点」作为起点，就是说将这个点作为坐标轴原点，就相当于把图像向上平移了。

这样，整个图像都保持在 x 轴以上，所以这个最低点 4，就是题目要求我们找的起点。

不过，经过平移后图像一定全部在 x 轴以上吗？不一定，因为还有无解的情况：

如果 sum(gas[...]) < sum(cost[...])，总油量小于总的消耗，那肯定是没办法环游所有站点的。就相当于上面那幅经过平移的图的最后一个点在 x 轴以下，所以无解。

反过来，如果 sum(gas[...]) >= sum(cost[...])，就相当于上面那幅经过平移的图中最后那个点处于 x 轴或 x 轴以上，就说明整个图像都在 x 轴以上，所以一定有解。

「贪心算法」

从头到尾遍历每个加油站，并检查以该加油站为起点，最终能否行驶一周。我们可以通过减小被检查的加油站数目，来降低总的时间复杂度。

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

这个结论很好证，因为在有余量的时候都到不了，作为起点(从 0 开始)肯定更到不了。

其实，你可以把这个解法的思路结合图像来思考，可以发现它们本质上是一样的，代码也相似，只是理解方式不同而已。

「滑动窗口」

将数组复制一份模拟环形数组。如果窗口内 sum>0，则扩张，否则缩小，当窗口长度为 n 时左边界就是起点。

直接套模板，代码如下：

区间调度问题

一个算法问题使用暴力解法需要指数级时间，如果能使用动态规划消除重叠子问题，就可以降到多项式级别的时间，如果满足贪心选择性质，那么可以进一步降低时间复杂度，达到线性级别的。

言归正传，本章解决一个很经典的贪心算法问题 Interval Scheduling（区间调度问题）。

无重叠区间

给定一个区间的集合 intervals ，其中 intervals[i] = [starti, endi] 。返回 需要移除区间的最小数量，使剩余区间互不重叠 。
注意只在一点上接触的区间是 不重叠的。例如 [1, 2] 和 [2, 3] 是不重叠的。

算法思路如下：

从区间集合 intvs 中选择一个区间 x，这个 x 是在当前所有区间中结束最早的（end 最小）。

把所有与 x 区间相交的区间从区间集合 intvs 中删除。

重复步骤 1 和 2，直到 intvs 为空为止。之前选出的那些 x 就是最大不相交子集。

把这个思路实现成算法的话，可以按每个区间的 end 数值升序排序，因为这样处理之后实现步骤 1 和步骤 2 都方便很多，如下 GIF 所示：

为什么要这样？因为是求最多能参加几个活动，找到活动最早结束的，这样就能赶紧参加下一个活动，就能参加更多活动，这就是贪心的策略。

代码如下：

用最少的箭头射爆气球

有一些球形气球贴在一堵用 XY 平面表示的墙面上。墙面上的气球记录在整数数组 points ，其中points[i] = [xstart, xend] 表示水平直径在 xstart 和 xend之间的气球。你不知道气球的确切 y 坐标。
一支弓箭可以沿着 x 轴从不同点 完全垂直 地射出。在坐标 x 处射出一支箭，若有一个气球的直径的开始和结束坐标为 xstart，xend，且满足 xstart ≤ x ≤ xend，则该气球会被引爆。可以射出的弓箭的数量 没有限制 。弓箭一旦被射出之后，可以无限地前进。
给你一个数组 points ，返回引爆所有气球所必须射出的 最小 弓箭数 。

其实稍微思考一下，这个问题和区间调度算法一模一样！如果最多有 n 个不重叠的区间，那么就至少需要 n 个箭头穿透所有区间。

有一点不同，这题边界触碰也算重叠。把 ≥ 改成 > 即可：

安排会议室

给你输入若干形如 [begin, end] 的区间，代表若干会议的开始时间和结束时间，请你计算至少需要申请多少间会议室。

换句话说，如果把每个会议的起始时间看做一个线段区间，那么题目就是让你求最多有几个重叠区间。

「暴力计算」

我们之前也学习过区间相关的算法，如果你对 差分数组技巧 有印象，应该首先能想到用那个技巧来解决这个题。

这道题相当于是说，给你一个原本全是 0 的数组，然后给你若干区间，让你对每个区间中的元素都加 1，问你最后整个数组中的最大值是多少。但是有一个问题，就是你必须把那个全是 0 的初始数组构造出来。由于我们用数组的索引表示时间，所以这个数组的长度取决于时间区间的最大值。

「扫描线」

基于差分数组的思路，我们可以推导出一种更高效，更优雅的解法。

我们首先把这些会议的时间区间进行投影：

红色的点代表每个会议的开始时间点，绿色的点代表每个会议的结束时间点。现在假想有一条带着计数器的线，在时间线上从左至右进行扫描，每遇到红色的点，计数器 count 加一，每遇到绿色的点，计数器 count 减一：

这样一来，每个时刻有多少个会议在同时进行，就是计数器 count 的值，count 的最大值，就是需要申请的会议室数量。

这里使用的是 双指针技巧，根据 i, j 的相对位置模拟扫描线前进的过程。

视频拼接

你将会获得一系列视频片段，这些片段来自于一项持续时长为 time 秒的体育赛事。这些片段可能有所重叠，也可能长度不一。
使用数组 clips 描述所有的视频片段，其中 clips[i] = [starti, endi] 表示：某个视频片段开始于 starti 并于 endi 结束。
甚至可以对这些片段自由地再剪辑：
例如，片段 [0, 7] 可以剪切成 [0, 1] + [1, 3] + [3, 7] 三部分。
我们需要将这些片段进行再剪辑，并将剪辑后的内容拼接成覆盖整个运动过程的片段（[0, time]）。返回所需片段的最小数目，如果无法完成该任务，则返回 -1 。

题目并不难理解，给定一个目标区间和若干小区间，如何通过裁剪和组合小区间拼凑出目标区间？最少需要几个小区间？

前文多次说过，区间问题肯定按照区间的起点或者终点进行排序。

因为排序之后更容易找到相邻区间之间的联系，如果是求最值的问题，可以使用贪心算法进行求解。

至于到底如何排序，这个就要因题而异了，这道题的思路是先按照起点升序排序，如果起点相同的话按照终点降序排序。

为什么这样排序呢，主要考虑到这道题的以下两个特点：

要用若干短视频凑出完成视频 [0, T]，至少得有一个短视频的起点是 0。

这个很好理解，如果没有一个短视频是从 0 开始的，那么区间 [0, T] 肯定是凑不出来的。

如果有几个短视频的起点都相同，那么一定应该选择那个最长（终点最大）的视频。

这一条就是贪心的策略，因为题目让我们计算最少需要的短视频个数，如果起点相同，那肯定是越长越好，不要白不要，多出来了大不了剪辑掉嘛。这里和前文跳跃游戏是相似的，如果你能看出这两者的联系，就可以说理解贪心算法的奥义了。

一个方法解决三道区间问题

所谓区间问题，就是线段问题，让你合并所有线段、找出线段的交集等等。主要有两个技巧：

排序。常见的排序方法就是按照区间起点排序，或者先按照起点升序排序，若起点相同，则按照终点降序排序。当然，如果你非要按照终点排序，无非对称操作，本质都是一样的。

画图。就是说不要偷懒，勤动手，两个区间的相对位置到底有几种可能，不同的相对位置我们的代码应该怎么去处理。

废话不多说，下面我们来做题。

删除被覆盖区间

给你一个区间列表，请你删除列表中被其他区间所覆盖的区间。
只有当 c <= a 且 b <= d 时，我们才认为区间 [a,b) 被区间 [c,d) 覆盖。
在完成所有删除操作后，请你返回列表中剩余区间的数目。

先按照起点升序排列，起点相同时按终点降序排列：

代码如下：

区间合并

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

按起点升序排列，有重叠时合并更新 res，没重叠时直接加入 res。代码稍微修改一下即可。

区间列表的交集

给定两个由一些 闭区间 组成的列表，firstList 和 secondList ，其中 firstList[i] = [starti, endi] 而 secondList[j] = [startj, endj] 。每个区间列表都是成对 不相交 的，并且 已经排序 。
返回这 两个区间列表的交集 。

题目很好理解，就是让你找交集，注意区间都是闭区间。

解决区间问题的思路一般是先排序，以便操作，不过题目说已经排好序了，那么可以用两个索引指针在 A 和 B 中游走，把交集找出来。

首先，两个区间存在交集的情况有哪些呢？穷举出来：

我们惊奇地发现，交集区间是有规律的！如果交集区间是 [c1, c2]，那么 c1 = max(a1, b1)，c2 = min(a2 ,b2)！这一点就是寻找交集的核心。

然后，我们的指针 i 和 j 肯定要前进的，什么时候应该前进呢？取决于 a2 和 b2 的关系，如下图：

将上面的总结为代码如下：

区间问题总结

第一个场景，假设现在只有一个会议室，还有若干会议，你如何将尽可能多的会议安排到这个会议室里？

这个问题需要将这些会议（区间）按结束时间（右端点）排序，然后进行处理，详见「无重叠区间」。

第二个场景，给你若干较短的视频片段，和一个较长的视频片段，请你从较短的片段中尽可能少地挑出一些片段，拼接出较长的这个片段。

这个问题需要将这些视频片段（区间）按开始时间（左端点）排序，然后进行处理，详见「视频拼接」。

第三个场景，给你若干区间，其中可能有些区间比较短，被其他区间完全覆盖住了，请你删除这些被覆盖的区间。

这个问题需要将这些区间按左端点排序，然后就能找到并删除那些被完全覆盖的区间了，详见「删除被覆盖区间」。

第四个场景，给你若干区间，请你将所有有重叠部分的区间进行合并。

这个问题需要将这些区间按左端点排序，方便找出存在重叠的区间，详见「区间合并」。

第五个场景，有两个部门同时预约了同一个会议室的若干时间段，请你计算会议室的冲突时段。

这个问题就是给你两组区间列表，请你找出这两组区间的交集，这需要你将这些区间按左端点排序，详见「区间列表的交集」。

第六个场景，假设现在只有一个会议室，还有若干会议，如何安排会议才能使这个会议室的闲置时间最少？

这个问题需要动动脑筋，说白了这就是个 0-1 背包问题的变形：

会议室可以看做一个背包，每个会议可以看做一个物品，物品的价值就是会议的时长，请问你如何选择物品（会议）才能最大化背包中的价值（会议室的使用时长）？

当然，这里背包的约束不是一个最大重量，而是各个物品（会议）不能互相冲突。力扣第 1235 题「规划兼职工作」就是类似的题目，在前面动态规划习题中做过了，动态规划+二分查找。

第七个场景，给你若干会议，让你最小化申请会议室的数量。详见「安排会议室」。