所有代码详见：https://github.com/jingminglake/Leetcode

总体思路

贪心的题目往往比较难，因为很难证明贪心策略是正确的。

至于贪心的解法，一般是求最优解，此时要做的不是暴力看所有的情况，而是局部步骤里面，选看似最优的结果，来进一步接近答案，就可以变成最后的解。

具体题目

738. Monotone Increasing Digits

题意：求比一个自然数小且单调递增的数中最大的那个。例如对于1002来说，答案是999.对于14436来说答案是13399。

解：寻找要求解答案的规律，发现，答案是原来的数从右向左看，第一个比自己右边大（违反递减）的数字可以减1，然后后面全部用9补齐。

注意相等的边界条件：

(1) 例如1455中第一个5违反递减规律，但是第一个5减1后，之前的4也会违反规律。因为1455的答案是1399，真正违反规律的是4。

(2) 例如17756，那么违反规律的是第一个7，而前7变为6后，前面的第一个7也会违反规律。

这里要做的就是只要出现违反，那么就立即就地减1，继续往前扫描。

452. Minimum Number of Arrows to Burst Balloons

题意：给出区间数组。把区间当作是气球，然后，区间点上射箭会让气球爆炸，现在求让全部气球爆炸的最小射箭次数。

解：此题是贪心，方法就是先排序，然后，看每个区间和之前区间的关系，如果之前区间里面的箭可以把当前区间射爆，那么不操作，

否则，要加新的一箭，然后再看下一个区间。

第一种排序方式是按左端点的由小到大排序，这种方式里面，例如遇到[1,6]和[3,8]，那么就在6这个地方来一箭，

至于后面区间，有三种情况：

情况一：如果是[5, 12]，那么这个区间会被6这一箭射爆；

情况二：如果是[7, 12]，那么就不会被6这一箭射爆；

情况三：如果是[4, 5]，那么这个区间可以被射爆，但是需要把之前射箭的地方从6改为5。

所以，对每个区间处理的时候，要更新当前一箭射在那里，其实就是在前面两个重叠区间里面较小的结尾处。

如果需要新的一箭，那新的一箭的位置在哪里呢？暂且放在当前区间的右端点，如果下次找到重叠区间，那么再更新回重叠区间中的较小结尾。

第二种（推荐）是按照区间的右端点排序。每个区间处理的时候，看之前选的箭的位置是不是可以把自己射爆（第一个区间默认在结尾处射箭）；

如果当前区间的起点落在之前的箭位置之前，就是可以射爆，此时就跳到下一个区间继续处理；

如果当前区间起点落在之前的箭位置之后，那么不可以射爆，那么就来新的一箭，新的一箭的位置是当前区间的右端点。

435. Non-overlapping Intervals

题意：给出区间数组，求最少要移除多少个区间，才能让剩下的区间互不重叠。

解：本质是贪心，而且是贪心里最经典的那一类——区间调度最大化（interval scheduling / activity selection）。

策略是：按结束时间升序排序，然后能留就留。

last = 负无穷
for 每个区间 (s, e)，已按 e 升序:
    if s >= last:   留下，last = e        // 注意是 >=，端点相接算不重叠
    else:           removals++

一遍扫描直接数出要删几个，不需要先算「能留几个」再去减。

为什么”按结束时间”是对的（交换论证）

一定存在一个最优解，包含「结束最早」的那个区间。证明：取任意最优解，设它里面结束最早的区间是 x，再设全局结束最早的区间是 e，则 e.end <= x.end。把 x 换成 e——最优解中其余区间都在 x.end 之后开始，自然也在 e.end 之后，所以换完仍然互不重叠，个数不变，依然最优。于是可以放心选 e，剩下的问题递归成同一个形态。

直觉版：结束得越早，给后面留的空间越大。这是唯一一个”贪”的地方。

其他看似合理的策略都是错的

按开始时间最早：[[1,100],[2,3],[4,5]] → 先选 [1,100]，后两个全冲突，只留 1 个删 2 个；正确应留 [2,3] 和 [4,5]，只删 1 个。

按区间最短：[[1,5],[4,6],[5,9]] → 最短是 [4,6]，选它之后另两个都冲突，只留 1 个删 2 个；正确应留 [1,5] 和 [5,9]（端点相接，本题算不重叠），只删 1 个。

按结束时间最早（正确）：同一组数据排序后是 [1,5] [4,6] [5,9] → 留 [1,5]（last=5）→ [4,6] 的 4 < 5，删 → [5,9] 的 5 >= 5，留。删 1 个，正确。

与452的关系（这里容易记错）

452 求的是最少箭数，它等于最大「互不重叠」区间个数。注意是「不重叠」——「最大重叠区间个数」是完全不同的量（某一点上最多叠了几个区间），那是 253 Meeting Rooms II 的答案（253 本身不是贪心题，已移到《总结（二十三）》区间与扫描线）。

而且不能直接拿 452 的答案来减，因为两题对”重叠”的定义不同：452 里 [1,2] 和 [2,3] 在 2 处一箭可穿，算重叠；本题这种相接不算重叠。

反例 [[1,2],[2,3]]：452 答案是 1（一箭穿两个），本题答案是 0（两个都能留）。若用「总数 − 452答案」= 2 − 1 = 1，就错了。

正确的说法是：435 = n − m，其中 m 是在本题自己的定义下（端点相接算不重叠）能保留的最大互不重叠区间个数。实际编码直接数 removals 即可，不必走这一步。

家族对照

同一个「按结束时间排序」的骨架，四道题问的量不同：

435 和 452 只差一个等号——又一次「等号归属」。253 问的是另一个量，所以换了工具。

而 435 其实是 1235 里所有 profit 都等于 1 的特例，所以 1235 那套 dp 也能解 435，只是没必要。反过来一旦带权，贪心立刻崩（一个 profit=100 的长活打得过一堆 profit=1 的小活）。

等权则贪心，带权则 dp。这条分水岭是区间这一族的核心判别。

605. Can Place Flowers

题意：给出0和1的数组，1代表花，现在要向数组里面加入花，要求是花和花之间必须要有间隔。

解：贪心法。从头到尾扫描一遍数组，如果能放入花，那么就放。

621. Task Scheduler

题意：给出字母数组，字母代表一种任务，每种任务单位时间为1就能解决，在给出一个CPU间隔n，表示不同任务执行之间必须要有n个单位时间的间隔。例如：A任务执行后，必须要执行n-1个其他任务，然后才能重新执行A，如果没有那么多种类的任务，那只有空闲着单位时间了。要求解的是执行完所有任务花费的最少时间，任务执行顺序不受数组顺序限制。

解：本题有两条路，分属两类方法：解法一是贪心 + 模拟，解法二是数学 / 构造。两者不是竞争关系——解法一排出来的形状，正是解法二那个公式所描述的形状，所以解法一其实给解法二提供了正确性直觉。

解法一：贪心 + 优先队列模拟

把每种任务的剩余次数装进最大堆，然后一轮一轮地排：

• 每一轮最多安排 n + 1 个不同的任务（因为同一种任务两次之间要隔 n 个单位，所以一轮之内同种任务只能出现一次）
• 每轮从堆里依次取出剩余次数最多的若干个（最多 n+1 个），每个的剩余次数减 1，减完还大于 0 的再放回堆
• 如果这一轮取不满 n+1 个，说明种类不够，剩下的格子只能是 idle——但最后一轮不用补 idle，任务做完就结束了
• 堆空即结束，累计的时间就是答案

为什么必须挑剩余次数最多的（贪心的论证）：出现次数最多的那种任务是瓶颈，它决定了时间轴至少要被撑到多长。如果某一轮不去安排它、而去安排一个低频任务，那个高频任务的剩余次数就没降，后面反而更难填满——高频任务会越堆越多，最终不得不塞进更多 idle。所以每轮优先消耗剩余最多的，才能让瓶颈尽快下降。

复杂度是 O(总时间 × log 种类数)。这条路直观、不容易想错，但代码比解法二长不少，而且要小心”最后一轮不补 idle”这个边界。

解法二：数学 / 构造（推荐）

不去模拟，而是先想清楚最优解长什么样，再直接把长度数出来。

两个关键量

• maxN：出现次数最多的那种任务，出现了多少次。注意是频次，既不是任务种类数，也和题目给的 n 无关（代码里叫 maxCount 更不容易误读）。
• countMax：有几种任务的次数达到了 maxN（并列冠军的个数）。

为什么按 n+1 切成”行”

同一种任务两次之间要隔 n 个单位，也就是两次的位置至少相差 n+1。

推论：把时间轴按 n+1 切成若干行，同一种任务在一行里最多出现一次。 于是，一种任务出现 c 次，就必须占据 c 个不同的行。

这是整个构造的地基。出现次数最多的那个任务是瓶颈，它把时间轴钉成了固定骨架。

矩阵图

tasks = ["A","A","A","B","B","B"]，n = 2。A、B 各 3 次 → maxN = 3，countMax = 2。

        ←  n+1 = 3  →
行1:    A   B   _
行2:    A   B   _        ↑ maxN = 3 行
行3:    A   B            ↓
              ↑
        最后一行长度 = countMax = 2

• 前 maxN-1 行：每行都必须占满 n+1 格（没任务填就 idle，因为下一个 A 必须等位置到了才能上），共 (maxN-1) × (n+1)
• 最后一行：只有 countMax 格

答案 = (maxN - 1) × (n + 1) + countMax

代入：(3-1) × 3 + 2 = 8。排出来是 A B idle A B idle A B，正好 8。

最后一行为什么恰好是 countMax

对任意一种任务 t：

所以填的时候从上往下填：低频任务最多只有 maxN-1 个副本，前 maxN-1 行一定塞得下，够不着最后一行。末行剩下的就只有并列冠军，每种恰好一个。

换个输入验证：["A","A","A","B","B","C"]，n = 2 → maxN = 3，但只有 A 达到 3 次，countMax = 1。

行1:  A  B  C
行2:  A  B  _
行3:  A            ← 长度 = 1

(3-1) × 3 + 1 = 7，排出来 A B C A B idle A ✓

末行不用补满，因为后面没任务了，末尾的空格不计入时间。这也是公式写成 (maxN-1) × (n+1) + countMax 而不是 maxN × (n+1) 的原因。

边界：任务种类太多时公式失效

return max((maxN - 1) * (n + 1) + countMax, (int)tasks.size());

这个 max 不是补丁，是必须的。怎么想到要加它，有三条路：

（1）拿平凡下界撞一下公式。 总时间必然 ≥ 任务总数（每个任务至少占 1 个单位）。只要公式算出的值 < tasks.size()，不用管机制，就知道公式错了。这条路最实用——不需要理解溢出，只需要有拿下界自检的习惯。

（2）把参数推到极端。 n = 0 时显然答案就是 tasks.size()。代入 ["A","A","B"]、n = 0：maxN = 2、countMax = 1，公式给出 (2-1)×1+1 = 2，而真实答案是 3，当场崩掉。

（3）追问模型的隐含前提。 上面说”低频任务前 maxN-1 行一定塞得下”，其实默认了一行坐得下所有种类。一行只有 n+1 格，种类数一旦超过 n+1 就会往右溢出，矩阵模型失效。

例：["A","A","B","B","C","C","D","D"]，n = 1。一行只有 2 格却有 4 种任务。公式给 (2-1)×2+4 = 6，而真实答案是 A B C D A B C D = 8，全程零 idle。

换个直观问法就是：“idle 一定存在吗？” 公式的本质是”骨架 + 填不满的坑”，坑之所以是 idle，是因为没有足够多的别的任务去填。别的任务一多，坑被填满甚至填不下，idle 就一个都没有——这时答案就是任务总数本身。

提炼：闭式公式题的两个自检

这三条路是同一件事的三个入口。凡是推出闭式公式的题，交卷前固定做两件事：

闭式公式是”跳过了模拟”换来的，跳过的那些步骤里就藏着边界。公式越简洁，越要回头查它跳过了什么。

解法二的代码

int leastInterval(vector<char>& tasks, int n) {
    vector<int> cnt(26, 0);
    for (char c : tasks) cnt[c - 'A']++;

    int maxN = 0, countMax = 0;
    for (int x : cnt) maxN = max(maxN, x);
    for (int x : cnt) if (x == maxN) countMax++;

    return max((maxN - 1) * (n + 1) + countMax, (int)tasks.size());
}

两条路怎么选：面试里先说解法一（思路直观、好解释、不容易错），再说「其实可以直接推出闭式公式」并给出解法二，这样既展示了思考过程又展示了优化能力。只背公式的风险是——一旦面试官追问「为什么末行长度恰好是 countMax」或者「为什么要和 tasks.size() 取 max」，没有解法一的形状作支撑就答不上来。

PS.（1）统计 maxN 和 countMax 要在计数表上遍历，不能直接扫原数组。 （2）和 tasks.size() 取 max 时要显式转成 int，否则 size() 是无符号数会出问题。

484. Find Permutation

题意：给出n-1大小的串，由D和I组成，第i位为D代表第i位到第i+1位是递增的，第i位为I代表第i位到第i+1位是递减的。求1，2，…，n的排列中满足条件最小的那个。

解：求全排列然后验证时间复杂度太高，而题目中包含最这个关键字，因此考虑使用贪心。

方法就是一开始初始化为123..n，看相应位置是不是违反了对应的D和I的规律，如果反了，那么就翻转，其实就是看D出现的位置，把D出现的位置全部连续的做翻转就可以了。

316. Remove Duplicate Letters

题意：”cbacdcbc”变为”acdb”。意味着，删除全部重复字母直到每个字母剩余一个，我们从中间选取字典序的作为结果，也就是说从cbad, cdbc, acdb, bacd中选取acdb作为结果。

解：此题解法是贪心，扫描的时候，就记录下来当前扫描过的元素组成子数组中最优值，后面的基于这样的最优值来计算。

每个元素必须保留一个，也就是说，即便a排在最后，但是若只有一个a，这个答案里面a也是在最后。

所以关键就是遇到一个元素的时候，如果之后未扫描的序列中还有这个元素的时候，那么这个遇到的元素一定可以贪心删除，除非：出现abcaa这种情况，也就是需要保留第一个a。

所以一定可以删除的情况就是：如果遇到的一个元素，后面的序列中还有这个元素，且后面序列中出现一个次序比它小的元素。例如bacbb这种情况，第一个b一定可以删除。

但是删除b的时机是遇到a的时候。所以，b必须先被保存下来，在之后遇到a的时候再删除b，如果a后面还有b的话。

还有一种必删除的情况，就是如果扫描的元素在当前最优结果已经出现了，那么就直接删除。

优化之前最优结果的考量：当前最优”bafgh”，遇到c，c如果后面还有h，那么h可以去掉，但c后面如果没有h的话，那么这个h是必须保留住的，这就导致优化停止，

也就是前面的g即使比c大，但也没有办法被优化掉的，因为如果选择优化g，那么g会在最终结果里面排在h的后面（h..g），而这个绝对不会比已经存在的gh更优。

此题具体解法就是使用栈+hash。从左到右扫描整个字符串，栈一直维持当前最优的序列，如果当前字母是已经存在在栈里面了，那么对该字母不需要任何操作，否则

如果是比栈顶更小的字母时候，我们看栈顶元素是不是在后面还存在，如果存在，那么删除掉，否则保留，如果出现保留，那么不能继续优化，否则继续优化，直到栈空。

如果是比栈顶大，直接加入栈，并标记该种元素为已经访问。

PS. 此题与402题类似。

418. Sentence Screen Fitting

题意：给出行列数量以及单词数组，求填充行列的情况下，需要使用多少个数组。

解：此题一开始是以为模拟对每行每列进行填充就可以了，但是这样时间复杂度高。进一步观察知道对于每一行，必然会以某个单词开头进行填充，而绝不会出现以空格开头的情况，所以，在行比较多的情况下会存在大量的重复，就以题目中的rows = 2, cols = 8, sentence = [“hello”, “world”] 来看，如果每次都是模拟往每行里面填单词，每次填单词消耗cols的时间，那在rows很大的情况下，就是消耗rows * cols的时间，但是我们知道，只存在两种模式，就是hello__和world__。

所以，此题可以使用动态规划记忆化方式来减少出现重复时候的计算时间。

使用一个hashmap<int, int>来保存从数组中第i个单词开头，此行能放下多少个单词，扫描完全部行之后，总的能放下的单词数除以数组大小向下取整就是单词数组的数量。

另外一种解法是先把单词数组连起来，然后放入行进行匹配，这种解法相比于一个一个单词放入解法的好处是贪心，由于列比单词长度大的多，所以匹配策略就是尽可能的先多放单词，实在发现不行就进行回退：减一个看看，不行再继续减…

774. Minimize Max Distance to Gas Station

题意：给出加油站数组，数组里面的数字表示加油站在x轴上的坐标，现在又给出k表示可以新插入k个加油站，现在求插入后使得加油站间最大距离可以减少到多少。

解：先理论上解题，然后再看有什么具体方法解题。此题n-1个区间，然后要加入k个分割点，我们知道，一个分割点只能是处于某一个区间，而要达到最佳效果，那么分隔点必须要平分一个区间，例如一个区间内含有3个分割点，那么最佳策略就是三等分这个区间。

那现在就有一个贪心策略了，每次选择区间长度除以区间现有的分割点的结果中最大的那个区间，插入一个新的结点。为了保证每次选最大的，可以使用优先级队列。时间复杂度为O(k * logn)，空间复杂度为O(n)。可惜的是这种方法超时了，这种方法缺陷就是如果k太大，时间总是依赖k。

另一种方法就是使用二分法，使用二分法之后，发现可以屏蔽掉k对时间复杂度的影响。二分法的对象是区间的最大段长度x，x一开始是介于0到无穷（题目要求），但是对于每个最大段长度x，我们可以在O(N)的时间内验证其合不合法，方法就是把每个区间都按照最大长度切分，看能切成几块，切了之后加起来的数如果小于等于K，那么就合法，否则不合法。

理解：一开始从0到n之间有n-1个区间，现在通过多放入k个点分割多出来k个区间，所以我们知道这些点要切分其中的大区间来使得最后所有区间是更加均匀的。

其中要通过加入点来切割的那些区间（原来长度大于最大段长度的区间），最终内部每段的长度都是小于或者等于最大段长度的，而其他所有不加入点的区间，他们的长度本身就是小于等于最大段长度的，所以不引入新区间。结论就是：第一类通过加点来切割的区间除以最大段长度得出来的区间个数，加起来只会小于等于K。换句话说，就是新引入的K个区间最好每个的大小都和最大段长度x一样，如果其中有些达不到最大段，即其中蕴含的最大段数量不足，那么说明这个大小是合法的，也同时说明最大段长度可以进一步减小来优化；如果按最大段来切，切出来的区间数居然比K多，那么说明最大段太小，不合法。

358. Rearrange String k Distance Apart

题意：给出一个串和整数k，要求是重新安排串，使得相同字符之间间隔至少是k。返回重新安排的串，如果不存在就返回空。

解：此题使用贪心法，先放置字符个数最多的字符，再放置次多的字符。如果剩余的字母种类数比下一轮要放的空格数小，那么直接返回空，每一轮要放的空格数是k和剩余串长度len中的较小值，每放一轮后，该轮放入的字母的个数减1，然后进行下一轮。

仔细想来，题意是要求两个相同字符之间有间隔k，所以严格意义上来说，每一轮都要放入k个特殊字符，如果k大于当前剩余字符串长度，那么在之前的操作中k轮放入k个不同字符，可以完美的保证两个字符相隔k；如果k小于当前剩余字符串长度，那么说明此轮只能放入剩余字符串的长度的字符，而且只能是最后一轮。无论是哪一轮，都必须遵守放入特殊字符的条件，一旦不符合，马上就返回空。

此题使用的数据结构就是优先级队列，每次选择堆顶字符，然后弹出来表示此轮不能再选了，如果当前字母对应的次数仍然不为0，那么就加入一个临时数组保存下来，然后下轮之前将临时数组中的信息重新添加到优先级队列中去。

55. Jump Game

题意：整数数组里面数字代表可以跳到多少数字之后，从第一个数字出发，问能不能跳到最后一个数字。

解：只要遍历一遍数组就可以，每次走一步，并更新当前能走的最远位置，如果当前走的位置比当前能走的最远位置小且比最后一个位置小，那么就继续走，否则退出，然后比较当前位置是不是在最后一个位置上。也就是说一步步走一定能走到最后一个位置。

135. Candy

题意：数组代表小孩分数，现在要求分糖果，要求:

1. 每个人至少一个；
2. 如果一个人的分数比左右两边高，那么他领的糖果不能比左右人领的糖果数量少

求这样发的最少总糖果数。

解：贪心法。扫描两遍，第一遍从左到右，确保每个小孩不比左邻居小孩（分比左邻居高）拿得少；

然后第二遍从右到左，保证不破坏之前性质的前提下，保证不比右邻居小孩（如果分比右邻居高）拿得少。

例如： 1 2 2 5 4 3 2 从左到右，得到 1 2 1 2 1 1 1 (解释: 不大于就直接从1开始，大于就是之前值加1) 从右到左，得到 1 2 1 4 3 2 1 (解释: 大于就是选之前值加1或者自己本来值中的较大者)

• 上一篇
  Leetcode按题目类型总结（十四）
• 下一篇
  Leetcode按题目类型总结（十六）