贪心算法：面试通关核心策略与实战

可视化演示

展示贪心算法局部最优选择过程，活动安排经典问题求解，以及最优子结构性质的递推验证。

贪心算法直觉：先拿最顺眼的菜

小周走进自助餐厅时，其实根本没想好 90 分钟里要吃什么。他的规则很简单：每轮绕场一圈，从眼前还没拿过的菜里，挑“当下最想吃的”那一盘。拿完就走，绝不回头，也不因后面出现了更好的菜而后悔。这就是贪心算法最核心的直觉：用当前可见的最优选择，代替对未来的全盘规划。

在算法里，这道“最顺眼的菜”通常用一个评价函数来量化。比如做区间调度时，我们评价“结束时间最早”；做跳跃游戏时，我们评价“能到达的最远位置”。每一轮都在候选集里选出这个评价最高的元素，然后更新状态，重复执行。贪心不像暴力搜索那样试遍所有路径，它只走一条不回头的主线。

这个策略听起来很“莽”，但它恰恰解决了一大批面试题。许多贪心题的第一步是排序：把候选元素按某个键排好，再从头到尾扫一遍。排序的目的，就是让“每次选当前最优”变成“当前指针指向的位置天然就是最优”。

小周之所以敢这么吃，是因为在这家餐厅，先拿哪道菜不会影响后面菜品的出现顺序，也不会占用额外资源。真实题目也一样：如果“当前拿了什么”会影响后续决策，贪心就未必成立；如果影响不大，贪心往往就是最快的答案。

两大支柱性质：为什么这顿饭能吃饱

小周试了几次发现，光靠“当下喜欢”还不够，除非餐厅有两个隐藏机制：第一，某道菜一定出现在某种最优吃法中；第二，拿走这道菜后，剩下的问题依然是“从剩余菜里选最优”，子问题和原问题长得一模一样。在算法里，这两个机制就是贪心选择性质和最优子结构。

以“会议室安排”为例：有若干会议，每个会议有开始时间 \(a_i\) 和结束时间 \(b_i\)，要选出最多互不冲突的会议。贪心策略是每次选结束时间最早的会议。为什么这样对？因为结束时间最早，就给后面的会议留下了最大的剩余空间。如果某个最优解第一个选的是会议 \(j\)，而贪心选的会议 \(g\) 结束更早，那把 \(j\) 换成 \(g\) 后，后面所有会议依然可以原样安排，不会变得更差。

这种“把最优解里的元素换成贪心元素”的操作，叫做交换论证。交换后解不劣，就说明贪心选择是有资格进入某个最优解的。接着再用数学归纳法或反证法补完，就构成了完整的正确性证明。这部分面试中不一定要求手写全证明，但至少要说得出思路。

有了这两根支柱，贪心就不是“赌运气”，而是“有证明的快速算法”。面试时如果能主动说出“这题满足贪心选择性质和最优子结构”，就已经比大多数候选人高一个段位。

实现框架复杂度：先排队再打饭

小周后来总结出自己吃自助餐的标准动作：第一步，先绕着餐厅走一圈，把所有菜按“心动程度”从高到低排个序；第二步，从心动值最高的菜开始，一盘一盘看，能拿就拿；第三步，每拿一盘，更新一下托盘剩余空间。这就是贪心算法的三段式框架：排序、循环、更新。

大部分贪心题的实现代码都极短，往往不超过二十行。真正决定效率的，常常是排序这一步。假设候选集合大小为 \(n\)，排序的代价是 \(O(n\log n)\)，之后只需线性扫描一遍。更新状态的代价通常是常数或对数级。因此，贪心算法的总复杂度主要由排序决定。

面试里写代码之前，先说出复杂度，会让答案显得更完整。通常说完 \(O(n\log n)\) 之后，还要补一句“空间复杂度是 \(O(n)\)，因为要存结果或临时列表”。这样面试官就知道你不只会背模板，还清楚每一部分的开销。

其实很多贪心题在排序之前毫无头绪，一旦排序键想清楚了，代码就是顺水推舟。小周也发现，提前“排队”能让他不再纠结：菜已经按心动值排好，直接照着顺序拿就行。

区间调度实战：让会议室高效转起来

有一类面试题会让小周特别熟练：公司只有一个会议室，各部门提交了使用时间段，问最多能排几场会议。这里的候选元素是若干区间，每个区间有开始时间 \(a_i\) 和结束时间 \(b_i\)，目标是选出的区间两两不重叠，并且数量最多。

贪心解法是：把所有区间按结束时间从小到大排序，然后从第一个开始扫描；只要当前区间的开始时间不小于上一个被选区间的结束时间，就选它，否则跳过。这样选出的区间数量就是最大化的。为什么不是按开始时间排序？因为一个区间结束得越早，越不会遮挡后面的会议，相当于小周在自助餐里先拿走“占时最短”的菜，给后面留出更多胃口。

这道题也是“分发饼干”“最少硬币”等经典贪心题的“母题”：先确定排序键，再确定可行性判断条件，最后更新状态。区间调度本身还会变形为“最多观看节目数”“最多完成工作数”，但解法骨架完全一致。

小周在自助餐厅也遇到过类似场景：有些菜需要排队等很久，如果先拿等待时间短的菜，反而能在同样时间里吃到更多种类。区间调度题的精髓，就是把“怎么选最多”变成“选最早结束的”，一次扫描，答案自现。

跳跃游戏实战：看得见的最远一步

小周吃完饭，在公园里玩“跳石头”游戏。每块石头上写着一个数字，表示“从这里最多还能往前跳多远”，他想知道能不能跳到对岸。最笨的办法是枚举每一种跳法，但小周只用记住一件事：到目前为止，能跳到的最远石头是哪一个。

贪心解法也很简单：从左往右遍历每一块石头，不断更新“最远可达位置”。只要当前位置不超过最远可达位置，就说明当前石头是够得到的；如果遍历过程中最远可达位置已经覆盖了终点，就说明可以跳到。这个思路在“最少跳跃次数”的变体中同样有效：每次走到当前覆盖范围的边界时，跳跃次数加一，同时把边界更新成当前能到达的最远位置。

这个问题的绝妙之处在于，它不需要记录具体路径，只需要一个变量持续滚动更新。很多看起来需要回溯的题，其实都可以用这种“边界+最远可达”的贪心框架解决。

小周的移动方式看似走一步看一步，但他其实一直在计算“最远能到哪儿”。面试里遇到跳跃游戏，先想清楚边界变量，再写循环，代码很快就能落地，而且不容易漏掉边界条件。

贪心与动态规划：自助餐与全桌计算

如果自助餐规则变成“拿了一道菜，就会改变其他菜的味道”，小周的“不回头”策略就可能失败。这时他需要另一种思路：像服务员一样，把菜单上所有搭配都算一遍，再挑最好的一组。这就是动态规划。动态规划用一张表记录所有子问题的答案，虽然慢，但一定安全。

贪心与动态规划最典型的对比是 0-1 背包问题：有若干物品，每个有重量 \(w_i\) 和价值 \(v_i\)，背包容量为 \(W\)，问最多能带走多少价值。按“单位重量价值”做贪心在有些用例上会失败，因为物品不可分割，选了一个大而轻的物品，可能挤掉两个小而重的组合。动态规划则通过填表枚举每一种容量下的最优组合。

面试时，如果一时分不清该用哪个，可以先试探贪心：构造一个反例，看它会不会翻车。找不到反例，再试着用交换论证说明贪心成立；如果明显存在反例，就果断转动态规划。贪心像小周凭感觉快速吃一轮，DP 像后厨把所有菜谱都算一遍。

贪心并不是动态规划的劣化版，而是“快速通道”。一旦题目确实满足贪心性质，它的实现和时空开销都远优于 DP。小周把这两种方法放在餐厅场景里理解：贪心是边走边选，DP 是先把整个菜单翻开算一遍；面试官更希望你先判断清楚该走哪条路。

面试套路与避坑：五步检票流程

小周在模拟面试中总结出一套“过检票口”的流程：看到题目，先不急着写代码，而是问自己三个问题：候选集合是什么？排序键是什么？可行性判断条件是什么？这三个问题想明白，贪心题就解决了一半。

第二步是构造反例。拿硬币面值 \(\{1,3,4\}\) 凑 6 元举例：如果每次优先拿面值最大的，贪心会拿到 4、1、1 共三枚；但最优解是 3 和 3 两枚。这说明贪心的排序键不是万能的。面试中，一个反例就能让你避免写出注定错误的代码。第三步是检查边界，比如列表为空、只有一个元素、所有区间完全重叠、金额为 0 等情况。最后再分析时间复杂度和空间复杂度，给面试官一个完整方案。

小周把反例当作“验票员”：通过验票，贪心方案才允许进入下一轮；通不过，就换用动态规划或其他方法。面试中最大的加分项，往往不是你一次写对，而是你能主动说出“这里我考虑过反例，所以选择更稳妥的解法”。

AI 应用场景

Python 演示

def max_non_overlap(intervals):    intervals.sort(key=lambda x: x[1])    picked = []    last_end = float('-inf')    for start, end in intervals:        if start >= last_end:            picked.append((start, end))            last_end = end    return picked  def min_jumps(nums):    n = len(nums)    if n <= 1:        return 0    jumps = 0    cur_end = 0    farthest = 0    for i in range(n - 1):        farthest = max(farthest, i + nums[i])        if i == cur_end:            jumps += 1            cur_end = farthest            if cur_end >= n - 1:                break    return jumps  def greedy_coin_count(coins, amount):    coins.sort(reverse=True)    count = 0    rest = amount    for coin in coins:        while rest >= coin:            rest -= coin            count += 1    return count if rest == 0 else -1  if __name__ == '__main__':    meetings = [(1, 3), (2, 5), (4, 6), (5, 8), (7, 9)]    print(max_non_overlap(meetings))    print(min_jumps([2, 3, 1, 1, 4]))    print(greedy_coin_count([1, 3, 4], 6))

1. intervals.sort(key=lambda x: x[1])这是区间调度的关键：按结束时间从小到大排序，让贪心选择天然可见。
2. if start >= last_end:判断当前会议会不会和上一个被选会议冲突，不冲突才收下。
3. picked.append((start, end))把选中的区间加入结果列表，同时后续更新 last_end。
4. farthest = max(farthest, i + nums[i])跳跃游戏的核心更新：不断刷新最远可达位置。
5. if i == cur_end:走到当前边界时，必须再跳一次，同时把边界更新成 farthest。
6. coins.sort(reverse=True)硬币找零的贪心排序：面值从大到小尝试。
7. while rest >= coin:只要还能用当前面值，就尽量多拿，这是典型的“当下最优”动作。
8. return count if rest == 0 else -1如果剩余金额不为 0，说明贪心在这个面值组合下失败。

常见误区

面试题