一聊到贪心算法很多人会拍着大腿说这我懂下一步怎么走。但真正落到代码里尤其是刷题、面试、做资源调度项目的时候就会发现它既是最容易上手的算法也是最容易翻车的算法。我见过不少同事和新人把贪心当成“每一步都看着顺眼就选哪个”结果在隐藏用例上栽了跟头回头排查往往不是代码写错了而是贪心策略本身就不成立。这篇文章想聊透的就是贪心算法的底层逻辑、几个经典入门模型、正确性证明的基本思路以及实战中怎么判断“这道题到底能不能贪”。如果你是刚开始学算法、准备面试或者工作几年想系统补一下算法底子的工程师这篇应该能派上用场。1. 从找零钱说起直觉贪心为什么会翻车1.1 一个看起来根本不需要思考的问题假设你买了一杯奶茶价格 79 元你掏出一张 100 元付给收银员收银员想找给你最少张数的纸钞。绝大多数人不用算下意识就会这么做先拿一张 50 元再拿一张 20 元再拿一张 5 元和四张 1 元。这个过程的本质是什么是每一步都选择当前还能用的最大面额直到凑满要找的金额。每一步都选最大面额最后用的纸币数量最少这个直觉在生活中几乎不会出错因为货币面额的设计本身就是为了让这种策略成立。这个“每一步都取当前最优”的算法就是贪心算法的雏形。它的关键在于贪心决策只盯着眼前的局部最优做完之后永不回头。不像背包问题里还要考虑“这个选了后面会不会不够空间”贪心算法一旦选定就不存在撤销重来的环节。正因为没有回退算法才快也正因为没有回退它才可能选错路。1.2 面额一换直觉瞬间失效现在我们把面额体系改一下改成只有 1 元、3 元、4 元三种硬币请问凑出 6 元最少需要几枚用“每次选最大面额”的贪心思路走一遍先拿 4 元剩 2 元没有 3 元可拿拿两个 1 元。总共是 411三枚硬币。但最省的做法明明是 33只需两枚。在这个例子里贪心给出的答案和最优答案是冲突的而且不是代码实现误差是策略本身错了。为什么会错关键出在“局部最优能否推出全局最优”这个前提上。用 4 元确实在一开始吃掉了很多钱但它把剩下的金额逼到了一个没法用 3 元整除的余数上。换成 3 元虽然单次拿得更少却给后面的组合留出了机会。这让我想起一个生活中的类比爬山路上看着某个山顶很近先冲上去再说结果冲上去才发现中间隔了一条深谷对面那个更高的山才是你真正该去的方向。贪心算法就是那个只看眼前海拔的人。通过这个小例子我们可以提炼出贪心算法成立的两个必要条件贪心选择性质和最优子结构。前者说的是当前这一步的局部最优选择必须有可能出现在全局最优解里后者说的是做完这一步之后剩下的子问题依然能用同样的贪心规则继续求解。两个条件缺一不可这基本就是判断一道题能不能用贪心的总纲领。2. 四个入门模型把贪心的套路摸清楚很多人学贪心卡在“看题的时候不知道按什么来贪”。实际上经典问题就那么几个套路把它们吃透很多变形题都能一眼穿过去。下面这四个模型是我觉得入门最值得花时间的。2.1 活动选择结束时间才是真正的优先级活动选择问题的经典描述是一天之内有若干场会议每场会议有开始时间和结束时间问最多能参加几场不重叠的会议。最容易想到的贪心规则是按开始时间早的优先或者按持续时间短的优先但这两个都是错的。正确做法是按结束时间从小到大排序每次都选当前结束最早、且与已经选中的会议不冲突的会议。为什么结束时间最关键因为选一个活动本质上是在“消耗”一段从开始到结束的时间窗口。结束时间越早留给后面的活动空间就越大。开始时间早不代表结束早可能一个从早上 8 点到下午 5 点的大会会把一整天都堵死持续时间短也不代表整体空间占用小比如中午 11 点到 2 点虽然只有三小时却恰好卡掉了午餐时段前后两场小会。这个例子在程序里经常被我拿来解释调度问题在很多任务调度的初级版本里只要把任务按截止时间排序再贪心选效果就比按优先级拍脑袋好得多。2.2 分饼干从小到大的双指针贪心LeetCode 的经典题“分发饼干”也很适合入门。有一群孩子每个孩子有一个胃口值有一些饼干每块饼干有一个尺寸值。一块饼干能满足一个孩子当且仅当饼干尺寸大于等于孩子的胃口值。问最多能满足几个孩子。最稳的贪心做法是分两步走把孩子胃口和饼干尺寸都从小到大排序然后用两个指针从最小的孩子和最小的饼干开始匹配如果当前最小饼干能满足当前最小胃口就给他吃两个指针都往后走如果不能满足就说明这块饼干连胃口最小的孩子都满足不了留在手里对谁都没用直接丢掉看下一块更大的饼干。为什么不是反过来用大饼干去硬顶小胃口因为大饼干是稀缺资源应该留给后面胃口更大的孩子小饼干虽然有局限但对小胃口的孩子来说可能是唯一解。把“最差的资源优先分配给最不挑的对象”这个思想在很多资源分配类问题里都能复用。2.3 哈夫曼编码每次合并最小的两个权值哈夫曼编码是贪心在压缩算法里的经典应用。给出一堆字符和它们出现的频率需要给每个字符分配一个二进制编码要求编码后总长度最短。贪心过程很简单把每个字符看成树的一个叶子节点反复从集合中取出两个权值最小的节点合并出一个新的节点权值等于二者之和然后把它放回集合直到只剩一棵树。为什么每次都合并最小的两个因为合并在编码树里相当于“让这两个节点往根的方向走一层”每往上层走一步意味着这两个字符的编码长度多了一位所有叶子节点的总编码长度就会增加相应的权值。为了让总长度增加得最少自然要让当前权值最小的两个节点为这“多出来的一层”买单。打一个比方一个团队的办公桌安排越常来找你的同事应该坐得离你越近而不是让那个一年来一次的人占着最近最方便的位置。哈夫曼编码做的就是这个事。2.4 Kruskal 最小生成树按边权从小到大“能加就加”最小生成树问题的 Kruskal 算法也是贪心的典型代表。把图里所有边按权重从小到大排序然后依次取出每一条边如果这条边连接的两个点目前还没有连通就把这条边加入生成树否则跳过重复这个过程直到所有点都在同一棵树上。这里的贪心对象不是点而是边。每次选剩下的最小权值边只要不构成环就保留。为什么不会后悔因为如果在某个连通状态下一条权值更小的边能把两个不同连通块连起来那任何最终生成树里这两个连通块之间必然也有某条边充当桥梁用当前这条更小的边替代那座桥梁总权值只会更小不会更大。这个结论在工程里做网络铺设、集群骨架拓扑设计时特别常用。而且它顺带告诉我们一件事贪心的“决策对象”是灵活的选点、选边、选区间都可以关键是找到那个能量化比较的优先级。3. 贪心和动态规划的分水岭别把所有优化题都往贪心里套看完整套模型可能有人会产生一种错觉好像只要排序加一个循环就行。这是最大的误区。贪心固然简洁但它的适用范围其实相当狭窄。我平时带新人时最常说的一句话是如果你不知道这道题为什么能贪那大概率不能贪。3.1 先分清两个性质再谈做题前面提过贪心成立需要两个条件。最优子结构比较好理解一个问题的最优解包含子问题的最优解。但光有最优子结构动态规划也具备所以它并不是贪心的专属标签。真正把贪心和动态规划区分开来的是贪心选择性质每一步的局部最优选择不依赖于后面的选择而且这个选择必须包含在某个全局最优解中。翻译成人话你可以先做这一步的决定做完之后不用担心将来会后悔。很多问题动态规划能解但贪心不能解就是因为这步决定会堵死后面的路。比如经典的 0-1 背包问题你在前面用贪心装性价比高的物品装到后面发现剩余容量装不下更多更优的组合了只能把前面拿的吐出来重新配。这种情况就没有贪心选择性质你就得老老实实做动态规划。3.2 面对一个优化题我实际的做法在没有标准答案的情况下判断一道题能否用贪心我有一套自己的三步法在面试和实际项目里都还算好用。第一步肉眼构造反例。先假设某个看起来合理的贪心规则比如“每次选权重最大的”“每次选覆盖最多的”“每次选消耗最小的”然后刻意构造几个边界数据专门盯着局部最优把全局带进沟里的情况。如果反例构造出来了直接转动态规划或剪枝搜索如果怎么构造都找不到反例进入第二步。第二步小规模暴力对拍。写一个绝对正确的暴力方法比如 DFS 枚举所有方案或动态规划然后用随机生成的小数据反复对比贪心结果和暴力结果。这一步相当于用计算机帮你做“反例二分查找”如果随机几千组数据后两边结果完全一致再进入第三步。第三步才是在心里做一个非正式的证明想想能不能用反证法说明贪心解不可能比最优解更差。这三步走完我才敢放心地把贪心策略写进最终方案。3.3 贪心、动态规划、搜索怎么选很多人喜欢背结论但我觉得更实用的是知道每条路线的成本和底线。下表是我对这三类思路的直观比较思路时间复杂度适用前提风险点贪心算法通常 O(n log n) 以下贪心选择性质成立策略错误结果直接失效动态规划O(状态数×转移数)最优子结构状态可枚举空间大状态设计难暴力/回溯指数级无约束规模一大就不可承受有一个特别典型的对照例子最大子序和问题。给定数组[-2, 1, -3, 4, -1, 2, 1, -5, 4]求和最大的连续子数组。很多人想不到这题能用贪心从左往右累加一旦前缀和变成负数立即把它丢弃从当前位置重新开始累加。为什么负数前缀可以丢因为它对后面所有子数组的和只可能是拖累不可能有贡献。这就是一个非常好的贪心选择性质案例。但是一旦问题变成“必须选出来的子数组长度是某个数”贪心立刻失效动态规划就该登场了。4. 证明思路从“感觉对”到“真的对”做算法题如果只看 AC 不追求明白大概率会在真实项目里吃亏。工程上一个贪心策略上线后跑正常数据怎么都对遇到极端数据就出问题而你又无法用穷举去验证全部场景这时候你就被自己的“感觉对”架在火上烤了。所以我强烈建议入门阶段就开始学三种最基本的证明方法。4.1 反证法假设贪心解不是最优导出矛盾反证法在算法证明里非常常用。思路是先假设贪心得到的解不是全局最优解那么一定存在一个不同的最优解它在某个决策点上和贪心解不一致。然后我们去检查第一个不一致的决策点把最优解里的那次选择替换成贪心选择证明替换之后整体结果不会变差。既然最优解可以不做任何牺牲地变成贪心解说明贪心解本身也就是最优解与假设矛盾。以活动选择问题为例假设贪心选了结束最早的会议 A而某个最优解第一个选的是会议 B且 A 不等于 B。因为 A 的结束时间不晚于 B 的结束时间把最优解里的第一个位置从 B 换成 A剩下所有会议依然完全不冲突。替换后的方案至少还是最优的这就说明“第一步选结束最早的活动”是安全的矛盾不成立。后面每一步套用同样逻辑贪心解就是最优解。4.2 交换论证把任意最优解逐步“洗”成贪心解交换论证是另一种很直观的方法。它不直接跟最优解比较而是说给我任何一个最优解我都能通过一系列相邻交换把它变成贪心解并且每一步交换都不让结果变差。那么贪心解当然也是最优解。拿分饼干问题来说假设某个最优解用一块比较大的饼干喂了一个胃口比较小的孩子同时有一块较小的饼干喂了一个胃口较大的孩子但我们知道小饼干满足不了大胃口所以这个组合一定是小饼干被浪费了或者被分配给了别的孩子。我们把两块饼干对调让大饼干分配给大胃口小饼干分配给小胃口满足的孩子数量只增不减。反复做这样的交换最优解就变成了从最小开始贪心的方案。这个过程尤其适合那些“两个序列都排序后配对”的题目几乎都能用交换论证套一遍。4.3 拟阵想研究透彻可以往这里走如果你想把贪心的适用范围从“这一道题”上升到“一类题”可以了解一下拟阵理论。拟阵是对“独立集”结构的一种抽象很多贪心算法之所以成立正是因为它们在某个拟阵结构上运行而拟阵上的贪心算法只要按权值从大到小或从小到大筛选独立集结果就一定是最优的。最典型的例子是图论中的“无环边集”构成一个拟阵。这就是 Kruskal 算法一定正确的深层原因它按边权从小到大加边同时保证不出现环本质上就是在拟阵上跑贪心。搜索引擎里常用的最大权生成树、任务调度中的截止期限安排也能归到拟阵框架下。你要是能看懂拟阵至少不会再觉得“贪心证明”是一堆碰运气的技巧因为它背后有一套完整的数学骨架。当然入门阶段不求精通知道这一层就够了。5. 实战踩坑经典题里的贪心陷阱与调试方法刷题和项目里真正让我觉得有价值的往往不是“这题我 AC 了”而是那些让我的贪心策略吃瘪的隐藏用例。下面这三个案例是典型的“看起来能贪、实际暗藏条件”的问题能帮你快速培养对贪心边界的敏感度。5.1 跳跃游戏 II一次跳最远不等于全局步数最少题目是这样的数组[2, 3, 1, 1, 4]每个数字代表你在当前下标最多能往后跳多远问从下标 0 跳到终点最少跳几次。很多人一上来就说每步都跳到当前能跳的最远位置那第一次从 0 跳到 2第二次从 2 最多跳到 3第三次才到 4总共三跳。这套做法在这个例子上居然是对的但它经不起推敲如果把数组改成[2, 3, 1, 1, 1, 1, 4]每步跳最远马上就可能绕弯路。正确的贪心思路是“区间推进”不去想具体跳到哪个点而是维护当前这一步的可达区间在遍历这个区间时不断更新下一步能到达的最远位置当遍历到当前区间的右边界时步数加一然后把这个最远位置作为新的区间右边界。这相当于每跳一步不是选一个点而是把一块“势力范围”整体往前推进最远距离直到覆盖终点。为什么这种贪心是对的最远距离覆盖了所有中间点往后能伸到的范围所以不存在某一跳能比你更新出的最远距离更远。这个思路在实现时有一个边界坑遍历到终点前就要停止更新步数否则最后一步会被多算一次。我可以很肯定地说这个 bug 几乎每个第一次写这个题的人都会踩一次。5.2 加油站累计油量为负时的断点判断加油站问题是另一个容易被表面贪心骗到的题。给出每个加油站的油量和到下一站消耗的油量问从哪个加油站出发能跑完一整圈如果不能就返回 -1。暴力的做法是对每个起点都模拟一圈O(n²)数据稍微大点就慢了。贪心做法很巧妙先用总和判断是否有解如果总油量小于总消耗直接返回 -1。如果有解从下标 0 出发累计剩余油量一旦在某个点发现累计剩余油量变成负数就以这个点的后一个点为新起点重新开始累计最后记录下来的起点就是答案。这个贪心挑起点为什么不担心漏掉因为如果从 start 开到 i 出现了负油量那就说明 start 到 i 之间的任意一个点作为起点开到 i 的累计剩余油量都必然小于等于负数不可能撑到终点。这其实又是一个“前缀和如果成为负数就放弃”的变体和最大子序和里丢弃负前缀的思路一脉相承。实际写这道题的坑是别在遍历完时就把最后一个累计值忽略要保证它用于判定最后一段路程。5.3 实战验证地对拍比脑补可靠得多不管做竞赛还是业务系统我都建议养成“对拍”的习惯。所谓对拍就是同时写一个高效的贪心实现和一个绝对正确但很慢的暴力实现用随机小数据反复让两份实现跑对比输出。import random def brute_solution(data): # 枚举所有可能方案返回最优值 pass def greedy_solution(data): # 当前怀疑的贪心策略 pass for _ in range(10000): data [random.randint(1, 30) for _ in range(random.randint(1, 8))] left brute_solution(data) right greedy_solution(data) if left ! right: print(找到反例, data, 暴力解, left, 贪心解, right) break这套方法在数学证明还没想通、又急着交付的时候特别有用。它能在一小时内用十万组随机数据快速暴露贪心策略的问题比你自己在那凭空构造反例有效率得多。一旦对拍发现不一致先不要改代码先拿反例去推导出正确的贪心优先级这是很多资深工程师都会走的路线。另外提醒一点涉及大量数据排序和累加时面试和生产代码里都要注意溢出的类型问题我在实际项目里就吃过因为 int 溢出导致贪心结果偏差的亏。6. 我的经验谈该贪就不要犹豫不该贪时果断换 DP最后聊点个人实践感受。贪心算法的学习曲线很短两三天就能把基础模型过完但它的能力边界很长真正会用的人往往是靠大量“被反例打脸”积累出来的。我自己刚入门时特别迷信贪心总觉得 O(n log n) 比 O(n²) 优雅太多后来在好几个项目里因为强行用贪心处理调度问题导致线上事故才慢慢学会了先验证再动手。现在我的判断习惯是看到一道优化题先花两分钟想清楚“这一步的选择会不会影响后面的可选范围”。如果不会就大胆用贪心快速对拍验证如果会影响二话不说转动态规划或搜索不要恋战。尤其是面试时一旦你向面试官提出贪心解法最好能当场给出反证法或者交换论证的关键步骤哪怕说不太严谨也比“我猜的”强得多。另一个特别有用的细节是把贪心的“决策依据”写进注释里。比如代码里“按结束时间排序”旁边我会注明为什么不是按开始时间。这种注释过两个月回头看能让你快速回想起当初的论证过程也能帮后来的接手者理解这不是一段随手排序。贪心算法就是这样短小精悍但每一行简洁背后都藏着一个“为什么不选另一个方向”的论证。把这份“为什么”想清楚才算真的入门了。