1. 贪心算法的核心一个选择加一个性质贪心算法大概是算法学习里最“反直觉”又最“直觉”的一个。说它直觉是因为决策方式很朴素——每一步都选当前看起来最好的选项不回头、不纠结说它反直觉是因为这类算法往往没有明显的套路可循同一个问题换个约束条件贪心就可能立刻失效。这篇文章就围绕贪心算法本身从它成立的底层逻辑讲起拆解两个核心性质再用经典问题完整走一遍“设计—实现—证明”的流程最后聊聊贪心与动态规划的边界以及我在实际刷题和工程中用贪心踩过的坑。这篇文章适合谁看刚学完基础数据结构和递归、开始接触算法设计的同学准备面试想系统梳理贪心套路的人以及工作中偶尔需要写启发式策略、想判断“面前这个问题能不能贪”的开发者。看完你应该能回答一个问题遇到一个优化问题我怎么快速判断贪心能不能用以及用了之后怎么证明它是对的。1.1 贪心选择性质局部最优如何变成全局最优所谓贪心选择性质是指问题的全局最优解可以通过一系列局部最优选择来构造。也就是说你不需要考虑未来的所有分支只要在当前状态选一个“看起来最好”的接着处理剩下的子问题即可。这句话听起来轻巧实际上是一个非常强的前提。绝大多数“贪心翻车”的案例都是因为问题压根不具备这个性质。比如背包问题如果物品可以分割分数背包按单位重量价值从大到小装贪心就是正确的如果物品不可分割0-1背包同样的贪心策略就会出错因为当前选一个“单位价值最高”的整件物品可能挤掉了两个组合起来更优的小物品。怎么理解这个性质我用一个生活类比你在自助餐厅想用“最少的盘子”装满“最多的菜”。如果每个菜都必须整盘拿0-1背包你每拿一盘都占一个盘子名额这时候“先拿最好吃的菜”未必是“总菜品价值最大”的解但如果菜可以随便拼盘分数背包那你永远可以优先夹“单位盘子面积价值最高”的菜这时候贪心就是对的。这个例子想说明的是贪心选择性质不是“我选了最好的所以正确”而是“无论怎么选至少存在一个全局最优解是从这个贪心选择开始的”。这是两回事。前者是感觉后者是可证明的结论。做题的时候如果只凭感觉很容易在变体题上翻车。1.2 最优子结构拆解后还是同一个问题最优子结构是指一个问题的最优解包含其子问题的最优解。这个性质保证了你在做了贪心选择之后剩下的子问题可以独立求解而不会牵一发动全身。继续用自助餐的类比你夹走了“单位面积价值最高”的那道菜之后剩下的问题变成了“在剩余盘子里用剩余容量装剩余菜品”这个子问题和原问题结构完全一样只是规模变小了。这种“自相似性”正是递归和贪心能成立的基础。最优子结构这一点贪心和动态规划是共享的。两者的区别在于动态规划会显式地枚举所有子问题的解再取最优贪心则只沿着一条“当前最优”的路径走到底。所以贪心更快——通常只要 O(n log n) 甚至 O(n)——但前提是这条路一定通向全局最优。还应该注意最优子结构不是“有递归结构”就自动成立的。有些问题看起来可以拆成子问题但子问题之间会相互影响。比如带互斥约束的任务选择选了任务 A 之后某些任务 B、C 都不能选这时候“剩余子问题的最优解”可能依赖“你没选 B、C”这个前提而不能简单套用原问题的解法。遇到这种“选择会改变未来选项集合”的问题要格外小心。1.3 判断“能不能贪”的三个快速问题很多初学者上来就背“排序加贪心”的模板结果一换题型就懵。我自己的经验是拿到一个问题先问自己三个问题这个问题能不能分成“做出一个局部选择 求解剩余子问题”的结构有没有一种“当前明显最优”的选择规则比如按截止时间最早、按收益最大、按区间右端点最靠左。能不能举出一个反例证明“按这个规则选择会导致整体更差”如果第三个问题暂时找不到反例而且前两个都成立那这个题目大概率可以用贪心。注意第三问非常关键——找不到反例不等于正确但它是通往证明的第一步。后面我会专门讲怎么用交换论证法把“找不到反例”变成“确实正确”。2. 经典案例实操三个问题完整走一遍光讲理论没意思我挑三个最经典的贪心问题把“设计—实现—证明”完整走一遍。这三个问题覆盖了最常见的三种贪心形态按区间端点排序、按最远覆盖范围递推、按双指针匹配。2.1 区间调度排序规则决定成败问题描述给定一组区间 [start, end]每个区间代表一个活动或任务选择尽可能多的互不重叠的区间。这个问题的经典解法是按 end 从小到大排序然后从左到右扫描每次选一个“结束最早的、且和已选区间不冲突”的区间。为什么按 end 排序而不是按 start 排序想象你要在一个会议室里安排最多的会议。如果按 start 排序你可能先选了一个“开始很早但一直开到晚上”的长会后面所有短会都排不进去了。而按 end 排序你优先给“最早结束”的会议腾位置剩余时间自然最多后面能塞下的会议数量只可能更多。代码实现Pythondef max_non_overlapping(intervals): if not intervals: return 0 intervals.sort(keylambda x: x[1]) count 1 last_end intervals[0][1] for start, end in intervals[1:]: if start last_end: count 1 last_end end return count注意一个细节判断重叠时我用的条件是start last_end也就是允许首尾相接。如果题目要求“两个区间不能共用一个端点”把条件改成start last_end即可这个细节在很多变体题里会影响答案。正确性证明用交换论证法假设存在一个最优解它的第一个区间不是 end 最小的那个区间 A。设这个最优解的第一个区间是 B。因为 A.end B.end所以 A 和最优解中第二个及之后的区间一定也不冲突——A 的结束时间不晚于 B而 B 与后面的区间都不重叠那么 A 与后面的区间自然也不会重叠。于是我们把 B 换成 A得到一个不更差的解。重复这个替换过程就能证明“包含 end 最小的区间”的最优解一定存在。这就是贪心选择性质后面的步骤用归纳法收尾即可。2.2 跳跃游戏用“最远可达距离”代替模拟问题描述给定一个非负整数数组 nums你从下标 0 出发nums[i] 表示你在位置 i 最多能往后跳多远问能否到达最后一个下标。我第一次做这个题时用的是 BFS 或者递归模拟复杂度很糟糕。后来才意识到这个问题根本不需要知道每一步具体跳到哪个格子只需要维护一个“当前能到达的最远下标”。贪心策略很简单从左到右扫描维护max_reach表示从已扫描过的位置出发最远能到达的下标。每次遇到一个位置 i如果 i 在可达范围内i max_reach就用i nums[i]更新 max_reach。最后看 max_reach 是否大于等于 n-1。def can_jump(nums): max_reach 0 n len(nums) for i in range(n): if i max_reach: return False max_reach max(max_reach, i nums[i]) if max_reach n - 1: return True return True这个贪心的精妙之处在于“合并了选择”在每个位置选择跳多远这个选择本身是自由的但我们不需要真的选只要保证“最远能覆盖到哪里”即可。只要最远覆盖范围能连成一条不断链的区间就一定能到终点。这其实是“能到达的区域是一个连续区间”这个观察的推论。顺带说一句变体题“跳跃游戏 II”要求输出最少跳跃次数仍然可以用贪心只是要把“当前一步能覆盖的边界”和“下一步能覆盖的边界”分开维护。这个变体稍微难一点但思路一致每次在当前的跳跃范围内找到能跳到的最远位置作为下一步的范围边界。这个题目是我认为练习贪心“从直觉到严谨”最好的过渡题之一。2.3 分发饼干双指针加排序的教科书组合问题描述有一组孩子的胃口值 g 和一组饼干尺寸 s每个孩子最多得到一块饼干且饼干尺寸必须不小于孩子的胃口值才能满足孩子。求最多能满足多少个孩子。这是最“模板化”的贪心题两个数组都排序然后双指针从胃口最小的孩子开始用尽量小的饼干去满足它。为什么不用大饼干去满足小胃口的孩子因为饼干不可拆分一个饼干只能给一个孩子用最小的能满足当前孩子的饼干可以把大饼干留给孩子胃口更大的孩子本质上也是一种“节省资源”的贪心。def assign_cookies(g, s): g.sort() s.sort() i j 0 while i len(g) and j len(s): if s[j] g[i]: i 1 j 1 return i这里有个调试细节值得说双指针里j无论如何都会前进而i只在饼干能满足孩子时前进。这段代码的正确性依赖排序后的大小关系是“单调的”——如果当前最小的饼干满足不了当前最小的胃口那它满足不了任何后面的孩子因为后面的孩子胃口只会更大直接丢弃如果它能满足就立刻分配。这个“单调性”是双指针贪心能工作的根基。很多人在写归并、数组去重、区间合并时栽跟头都是因为忘了先排序或者比较条件写反。3. 贪心和动态规划的分界线在哪里很多同学问过我“怎么判断一道题该用贪心还是动态规划”我的回答是先尝试贪心但要带着“验证”的心态去试一旦发现反例立刻转 DP。3.1 一个经典的“贪心翻车”案例零钱兑换面额体系为 1、3、4 元要凑出 6 元。贪心策略是“每次都选不超过剩余金额的最大面额”先选 4剩 2再选 1再选 1共 3 枚硬币。而最优解是 3 3只要 2 枚。这就是经典的贪心反例。为什么 1、3、4 会翻车因为选 4 这个“局部最优”把剩下 2 元逼到了一个只能用两个 1 来凑的尴尬境地。而 1、2、5、10 这种面额不会翻车是因为它们满足“规范硬币体系”的性质——每个面额能被更大的面额整除或者存在特定的结构保证贪心正确。这个案例说明即便一个问题的子问题结构是重叠的、可递归的也不代表贪心一定能用。零钱兑换问题的正确解法是动态规划因为状态转移天然是“选一枚硬币 剩余金额的子问题”而且子问题之间会重叠凑 6 和凑 5 都要计算凑 2 的结果。我当年第一次看到这个反例时整个人是懵的因为“每次选最大面额”实在太符合直觉了。但正是这个案例让我养成了一个习惯任何贪心策略先在小数据上暴力对比一下再往下写正式代码。3.2 贪心与动态规划的决策对比我把两者的差别总结成一张对照表方便你快速回顾维度贪心算法动态规划决策方式每一步只走一条“当前最优”的路径枚举所有可能的转移保留每个子问题的最优值时间复杂度通常 O(n log n) 或 O(n)通常 O(n²) 或 O(n × 状态数)需要证明什么贪心选择性质 最优子结构最优子结构 状态转移方程正确典型失败场景局部最优与全局最优不一致时翻车状态定义不完整时漏解但不容易“错得不明显”代码复杂度通常很简洁通常需要维护 DP 表或滚动数组有一句不算严谨但很好用的经验如果一个问题需要“在多个可行方案中比较后取最优”而且子问题之间有大量重叠大概率是 DP如果一个问题可以“找到一个显然的偏好规则且这个规则不会损害未来的选择空间”那就可以考虑贪心。3.3 快速判断“能不能贪”的经验法则我在实际做题中总结出几条快速判断的经验问题如果涉及“最大化数量”或“最小化成本”可以优先想想有没有单调排序的贪心策略。如果状态转移时当前选择会“永久性地消耗某种资源”比如容量、时间、名额贪心往往有戏——因为它本质上是资源分配问题。如果当前选择会“改变未来选项的可用性”比如选了 A 就不能选 B 的互斥约束要多留个心眼先去构造反例。只要构造反例时能找到一个“贪心选择和某个最优解冲突且无法通过交换补救”的案例立刻放弃贪心转 DP 或二分答案等其他思路。这条经验法则不保证 100% 准确但能帮你减少把时间浪费在错误方向上的概率。尤其是第 3 条几乎是我判断“这题有诈”的第一信号。4. 实战中躲不开的坑与排查方法即便你理解了贪心的原理实战里还是有不少细节容易翻车。我把自己踩过和帮别人 review 代码时见过的坑整理一下这部分内容常规教材里基本不会写。4.1 五个高频翻车现场翻车一排序维度选错。区间调度按 end 排但很多变体题要按 start 排或者按长度排。比如“合并重叠区间”就是按 start 排因为合并需要从左往右连续扩张而“选最多不重叠区间”要按 end 排。两个题长得像策略完全不同。我的建议是动手前先在注释里写清楚“我按哪个关键字排序为什么”写不出来就说明还没想透。翻车二边界条件没处理。空数组、只有一个元素、所有区间都重叠、饼干尺寸刚好等于胃口值——这些情况在贪心代码里最容易出 bug。特别是双指针类的题while i len(g) and j len(s)里两个条件的先后顺序一旦写错就可能数组越界或者漏掉最后一次匹配。翻车三相等情况处理不当。区间调度里 end 相同的区间选哪个都行但如果你在处理重叠时用了而不是就可能漏掉首尾相接的情况。排序算法不稳定或者比较器写错也会在相等时产生意想不到的结果。翻车四把“直觉”当成“正确”而不去证明。这个不算代码 bug但危害更大。我见过有人把“按收益从大到小贪”用在带互斥约束的任务选择问题上结果在数据规模稍大时直接算错。正确做法是先用反例测试几个小数据再尝试用交换论证法写一遍证明。哪怕最后证明不出来至少你心里清楚自己是“猜的”还是“有把握的”。翻车五忽略数值范围和类型问题。在跳跃游戏这类问题里i nums[i]可能超出语言默认整型的表示范围在特定语言里要注意溢出。另外维护max_reach时如果初始值设得不对比如第一个位置本身不可达且 n 大于 1循环逻辑要能正确处理这种情况。4.2 如何严谨地证明贪心正确性证明贪心正确性通常有两种思路实际做题时我建议都练一练。交换论证法假设存在一个最优解它和贪心解在某个选择上不同。然后证明把这个不同之处替换成贪心选择最优解不会变差。重复这个过程最终得到“存在一个从贪心选择开始的最优解”。区间调度就是典型的交换论证。归纳法证明贪心算法在“第一步”做出最优选择并且“剩余问题”仍然是一个同类贪心问题。具体来说先证明贪心选择性质第一步一定可以出现在某个最优解里再证明最优子结构把第一步拿掉后剩余部分必须也是剩余问题的最优解否则可以用更优的子解替换来导出矛盾。两步合起来就能用归纳法证明整条贪心路径正确。练习时可以在草稿纸上画“决策树 交换箭头”先把贪心解和一个假想的最优解并排画出来标出第一个分歧点试着把贪心选择“换”进去检查是否变差。这个过程很像调试代码——找到第一个分叉替换验证。多练几次你对“贪心为什么对”的理解会和背模板完全不一样。4.3 工程中贪心思想的落地方式最后说一个容易被忽视的方面贪心算法不只是刷题工具它在真实工程里非常常见只是名字不叫“贪心”。举几个例子任务调度器按“剩余执行时间最短优先”安排任务可以最小化平均等待时间这就是贪心缓存淘汰里的 LRU 和 LFU 本质上是基于局部性原理的贪心近似负载均衡里“把新请求发给当前连接数最少的节点”最少连接调度也是贪心。这些算法在理论上不一定保证全局最优但在工程约束下——数据规模大、实时性要求高、没有完整信息——贪心往往是“用最小代价换取可接受结果”的最佳选择。在实际项目中如果想用贪心做近似方案我建议至少做三件事用随机数据跑 Benchmark和小规模时的精确解枚举或 DP 求得对比误差明确记录贪心策略的前提假设比如“任务可抢占”“流量分布均匀”设置兜底逻辑在贪心输出明显不合理时能自动降级到更慢但更稳的算法。工程里没有银弹贪心只是工具箱里的一把好用的螺丝刀。最后再分享一个我自己的习惯每学一个贪心算法我都会在笔记里写一个“反例三件套”——一个会导致错误贪心策略的小数据、一个边界数据、一个大数据量下的性能验证。这个习惯帮我避开过很多“看起来对”的坑也让我从“背模板”慢慢变成了“能自己设计贪心策略”。贪心算法最迷人的地方恰恰在于它逼着你把“当前最优”的定义想清楚真正重要的是那个选择规则而不是算法本身。如果你也想深入理解这类问题建议从区间调度和跳跃游戏开始先抛开代码在纸上把“为什么按这个规则选”推演一遍再动手实现效果会比盲目刷几十道变体题好得多。