1. 贪心算法到底在贪什么很多人在刚开始接触贪心算法时第一反应往往是这不就是每一步都选最好的吗有什么好学的。但真正上手写过区间调度、跳跃游戏、哈夫曼编码之后才会意识到贪心是那种看上去很简单写出来才发现全是坑的算法。先说结论贪心算法是一种在每一步决策时都采取当前状态下最优选择从而希望最终达到全局最优的策略。它的核心不是贪而是每一步的局部最优恰好能拼出全局最优这件事本身是有限的、可证明的而不是碰巧成立的。这话听起来有点绕我用一个生活化的场景来解释。假设你要在一个行李箱里塞东西目标是装下尽量多的物品。一个最自然的办法是先把最大的物品放进去再用小物品填缝。这个策略能解决很多实际问题但它并不能保证在任何情况下都装得最多——有时候先放一堆中等大小的物品反而比先放一个超大物品装得更多。这就是贪心算法的核心矛盾局部最优并不总是全局最优。那为什么还要学它因为存在一大批经典问题它们的结构决定了贪心策略恰好是最优的比如找零钱、区间调度、最小生成树、单源最短路径Dijkstra算法本质上就是贪心。这些场景中贪心算法实现简单、运行效率高往往比动态规划节省大量时间和空间。这篇文章不是教科书式的长篇大论而是我个人从背模板到真正理解贪心的全过程记录。我会先用最通俗的方式讲清楚贪心的思想、两个核心要素和适用边界然后拆解几道高频算法题手把手把推导过程写给你看最后聊一聊如何判断一个问题是否能用贪心以及常见误区。无论你是刚学数据结构与算法的新手还是在准备算法面试这篇文章应该都能帮你在贪心这个主题上建立起完整的思考框架。2. 贪心的两个核心要素与一个致命陷阱2.1 核心要素一贪心选择性贪心选择性是指通过一系列局部最优选择能够产生全局最优解。换句话说你不需要回头看之前的选择也不需要尝试多种可能——每一步的决定是一条道走到黑的。举一个经典的例子——找零钱问题。假设有1元、5元、10元、25元四种面额要凑出63元贪心的做法是每次选择面额最大且不超过剩余金额的硬币先取25元剩余38元再取25元剩余13元再取10元剩余3元再取3个1元。总共6枚硬币这确实是最优解。这个场景之所以能用贪心是因为币制设计满足了一个特殊性质任一较大面额都是较小面额的整数倍关系所以尽量用大面额不会吃亏。但如果你把面额换成1元、4元、5元要凑出8元贪心会先取5元再取3个1元总共4枚而最优解是2枚4元。同样是找零钱贪心就失效了。这个反例说明贪心选择性不是所有问题的默认属性它需要被验证。2.2 核心要素二最优子结构最优子结构指的是——一个问题的最优解包含其子问题的最优解。动态规划也需要这个性质所以两者经常被放在一起比较。区别在于动态规划会枚举所有子问题的解并从中挑选贪心则只沿着一条路径探下去。回到找零钱的例子如果你已经决定先取25元那么剩下的凑出38元就是一个独立的子问题而且它的最优解必须被包含在整体最优解中否则整体就不是最优。这个性质保证了贪心每一步之后问题规模变小但性质不变可以继续用同一策略处理。2.3 致命陷阱局部最优不等于全局最优这是贪心算法最致命的地方。我最早学贪心时踩过最深的坑就是拿到问题直接套当前最贪的策略写完之后心里美滋滋一跑测试用例才发现结果不是最优。举一个非常直观的例子——背包问题不可分割物品即0-1背包。假设背包容量为10有三件物品分别如下A重量9、价值10B重量4、价值5C重量4、价值5。如果按性价比价值/重量贪心会先选A然后剩下的1单位容量啥也装不了总价值是10但如果选B和C总重量是8、总价值是10其实结果一样。换一组数据可能会让你看到更明显的反例容量10物品A重量9价值12物品B重量6价值8物品C重量5价值7。按性价比贪心会选A价值12而最优解是BC价值15。这就是0-1背包必须用动态规划的原因——贪心在这里无法找到全局最优。所以在动手写贪心代码之前必须先问自己三个问题第一这个问题的局部决策是否独立做完之后不用回退第二每一步的最优能否严格定义第三是否存在一个可以通过数学归纳或交换论证来证明的贪心策略如果对这三个问题都没底那大概率不能用贪心。3. 三道必刷高频题我把推导过程完整拆给你看光讲理论容易让人一头雾水这一章我会从经典题目出发把我的思考过程和代码一起写下来。这三道题分别对应不同的贪心策略类型区间类、可达性类、匹配类。把它们吃透很多变种题其实都是这三类的变形。3.1 区间调度怎么证明选最早结束的一定对题目描述很简单给定多个区间选择尽量多的互不重叠区间。这个问题的贪心策略是按结束时间从小到大排序每次选择结束时间最早、且与已选择区间不冲突的区间。教科书上通常会直接给出这个结论但我当年第一次看到时完全没想明白——为什么不是选开始时间最早的为什么不是选持续时间最短的现在用逻辑推一遍。假设你现在面对一堆还没安排的区间面前有两个候选区间A最早结束区间B是某个最优解里的第一个区间。如果A就是B完美如果A不是B那么A的结束时间一定不晚于B的结束时间因为A是最早结束的。既然A结束得更早它给后续区间留下的可用空间就不少于B所以把B换成A不会让结果变差。这就是贪心算法的交换论证——把最优解中的元素逐步替换成贪心选择的元素证明替换后仍然是最优解。思路清晰了代码其实很短。注意要处理边界条件区间重叠判断是当前区间的开始时间 上一个选中区间的结束时间而不是大于号因为首尾相接不算重叠这在题目中一般有明确说明。我用一个例子验证一下区间列表是[[1,4], [3,5], [0,6], [5,7], [3,8], [5,9], [6,10], [8,11], [8,12], [2,13], [12,14]]。按结束时间排序后依次检查选[1,4]接下来能和它兼容的最早结束区间是[5,7]再往后是[8,11]最后[12,14]总共能选4个。而如果贪心选开始最早的[0,6]最多只能选出3个。差别就在这一步。3.2 跳跃游戏每一步都拓展可达范围这个题的描述很有趣你站在数组的第一个位置数组里的每个数字代表你在这个位置最多能跳多远问你能不能跳到最后。我第一次做这题时第一反应是递归加记忆化搜索写了一堆代码后来才发现贪心才是最优解。核心思路是维护一个变量maxReach表示从起点出发能到达的最远位置。从左到右遍历数组只要当前位置在maxReach范围内就尝试通过当前位置跳到更远的地方更新maxReach为max(maxReach, i nums[i])。如果某一刻maxReach已经不覆盖当前位置说明中间断开了永远到不了终点如果maxReach已经大于等于最后一个下标直接返回true。这里不需要维护每一步具体跳到哪个位置也不需要回溯因为所有能到达的区域是连续的——只要i能到i1也有办法到这是由最多能跳的距离这个性质决定的。我用一个例子说明数组[2,3,1,1,4]从位置0出发maxReach一开始是2遍历到位置1能跳3步到位置4maxReach更新为4瞬间就确认能到终点。但如果数组是[3,2,1,0,4]前四个位置都在reach范围内但位置3能跳0步maxReach始终是3遍历到位置4时发现下标4 maxReach直接返回false。3.3 分发饼干排序后双指针匹配这道题是贪心匹配类的入门题题目背景是有一群孩子和一堆饼干每个孩子有胃口值每块饼干有尺寸值只有饼干尺寸大于等于孩子的胃口时孩子才能吃饱。问最多能让多少个孩子吃饱。解法很朴素两组数据都排序然后从胃口最小的孩子开始依次匹配当前能匹配的最小饼干。为什么这样贪心是对的因为小胃口的孩如果都喂不饱大胃口的更不可能喂饱——把大饼干留给大胃口的孩子比把大饼干喂给小胃口的孩子更划算。这本质上是一种资源分配策略最稀缺的大饼干要留给最需要的场景。这个题还有个小细节从哪个方向遍历比较合适通常是从小到大匹配因为如果从大到小你可能会把大饼干早早用掉后面遇到大胃口孩子时反而没有合适的饼干。实际编码可以用双指针一个指向孩子数组一个指向饼干数组匹配成功才移动孩子指针。这个题难度不大但它能帮你建立一种思维模式遇到匹配类问题先考虑排序再考虑贪心。4. 贪心 vs 动态规划 vs 回溯什么时候该用谁很多人在学习贪心时最大的困惑是这题一眼看上去很像动态规划到底该用贪心还是DP或者这题需要回溯穷举但数据规模大到没法穷举有没有更聪明的办法我的经验是不要试图从题目关键词来判断而要从问题结构来判断。这里列一个快速判断表是我自己常用的一套思路问题特征适合贪心适合动态规划适合回溯是否要求全局最优是是是局部最优是否导致全局最优是不一定不一定子问题是否重叠不需要需要通常不关注是否允许回退/探索多种可能不允许允许允许时间/空间复杂度要求极高效率中等效率低效但完整表格太抽象的话我说几个具体的判断信号。如果一个问题能分解成每做一步都缩小规模而且缩小后的子问题结构与原问题完全一致这强烈暗示贪心或DP都有戏。此时关键在于验证贪心选择性——如果能在纸上通过反证法或交换论证证明贪心可行就选贪心如果证明不出来但子问题重叠明显就用DP。举一个我常拿来区分的例子求网格路径最小和。从左上角到右下角只能向右或向下每个格子上有数字求路径上的数字之和最小。这个问题不能用贪心——你每一步选当前格子的右方和下方中数字较小的那个方向但有可能绕远路导致总和反而更大。正确的做法是DP把每个位置的最小路径和逐层递推出来。原因很简单路径的未来代价取决于当前选择之后的所有后续选择局部最优无法保证全局最优。再看另一个例子加油站问题。一个环形路线每个加油站能加油每段路消耗油问从哪个加油站出发可以走完全程。这个题有一个非常优雅的贪心解法一次遍历累计剩余油量当总剩余油量变为负数时把起点设为下一站。这个策略的严格证明依赖于如果总加油量大于等于总消耗量则一定存在可行起点这条数学结论。这类题的结构是存在性唯一性和路径最优类问题的结构完全不同。动态规划和贪心的选择说到底是对问题性质的判断而不是算法本身的偏好。我个人的习惯是能贪心就贪心因为代码短、常数小、不费内存贪心证明不出来就转DPDP状态都定义不清楚而且数据量小才考虑回溯。这个优先级反过来会非常痛苦——用DP硬解贪心题状态多到怀疑人生用贪心硬解DP题测试样例一多直接翻车。5. 如何证明一个贪心策略是正确的5.1 交换论证法把最优解逐步变成贪心解交换论证是我觉得最直观的贪心证明方法核心思想是假设存在一个最优解如果它不是按照贪心策略构造的我可以通过一系列交换操作把它逐步变成贪心解而且在交换过程中解的质量不会变差。以区间调度为例排序后贪心选择的第一个区间是结束时间最早的。某个最优解的第一个区间如果是另一个区间我就把后者换成前者。因为前者的结束时间不晚于后者与后续区间冲突的可能性更小所以总区间数量不会减少。接下来对第二个区间、第三个区间重复同样的操作最后会发现贪心解本身就是最优解。这种证明方式的优势在于你不需要从零推演贪心一定是对的只需要证明贪心不会比最优解差即可。5.2 归纳法从规模小的情况一步步推到大情况另一种常用方法是数学归纳法。假设贪心策略在前k步中已经证明是最优的证明第k1步的贪心选择也能保持最优性从而推广到任意规模。以跳跃游戏为例假设已经处理到第i个位置此时maxReach表示从起点能到达的最远下标。如果i1在maxReach内那么在i1位置更新最远距离不会丢掉任何原本可达的位置。这个性质可以归纳地证明遍历结束后如果maxReach覆盖了最后一个下标那么终点的可达性是成立的。归纳法特别适合那些递推式推进的贪心问题。5.3 反证法假设贪心不是最优的推出矛盾反证法在证明贪心时也很常用。逻辑是假设贪心选择的结果不是全局最优那么一定存在一个最优解在某个决策点处与贪心不同。然后通过一系列推导得出这个不同会导致矛盾从而证明贪心选择必然在某个最优解中。比如最小生成树的Prim算法和Kruskal算法教科书上通常就是用反证法结合切分定理来证明的。这类证明对初学者来说难度偏高我建议不用一开始就死磕严格证明先把交换论证和归纳法用熟练再回头补反证法的细节。实践中很多面试官能接受的证明要求并不高你只需要能用清晰的语言说明为什么当前选择不会错就够了但至少你要有证明的意识而不是拿测试样例通过作为算法正确的唯一依据。6. 常见误区与实操心法6.1 误区一把感觉对当成证明对了这是我见过最多的问题也是我自己的血泪教训。刷题平台上很多贪心题是有提示的比如题目标签就写着贪心你会下意识觉得这题贪心能做。但真实场景下没人给你贴标签你要自己判断。最稳妥的做法是在纸上写几组不同形态的测试样例特别是一些边缘情况——数据全相等、数据有序、数据完全乱序、超大超小混合然后问自己如果换一种贪心策略比如按开始时间排序、按持续时间排序结果会不会不同如果会那说明你的贪心依赖了某种特定排序需要仔细验证。6.2 误区二忽略排序与双指针的配合贪心算法里最常见的一个操作就是排序。不管是区间问题、分配问题还是部分背包问题排序通常是贪心策略的第一步。但很多人排序之后直接在原数组上做双指针结果出现边界错误。这个坑我在分发饼干上踩过——排序后没有注意数组长度可能不相等一个指针已经越界了还在循环里访问导致运行时错误。建议养成习惯双指针操作的循环条件里必须同时检查两个指针的有效范围。6.3 误区三贪心策略选对了却不会处理边界区间类问题的边界处理非常容易出错。比如[1,4]和[4,5]是否重叠有些题目说重叠因为4被两个区间共享有些题目说不算重叠因为首尾相接可以连续安排。这个细节直接决定你用还是。我的建议是拿到题目先确认重叠的定义如果题目没有明说看样例推断实在不确定就选保守的写法并在注释里说明假设让做题时思路更清晰。跳跃游戏类的边界问题同样常见下标从0开始会导致i nums[i]可能恰好等于数组长度减1这算可达终点但如果数组长度为1你已经在终点直接返回true不需要跳。这些edge case看起来不起眼实际却占测试用例的很大比例。一个经验法则是写完整洁的主逻辑后立刻用最小区间、最大区间、单元素数组、空数组、全零数组各测一遍。6.4 实操心法贪心题的五个自查步骤我刷题几年总结了一套贪心题的通用自查流程分享给你第一步明确目标函数是什么最大化还是最小化第二步列出所有可能的贪心指标——比如结束时间、开始时间、长度、价值密度、剩余空间等等不要只盯着一个想。第三步逐一试着验证每个指标是否满足贪心选择性常用方法是构造反例如果能快速构造出反例就说明该指标不行。第四步选定指标后确定排序方式升序还是降序然后用双指针或线性扫描实现。第五步用随机小规模数据跑暴力解法和贪心结果对比如果随机测试几百组都没有差异基本可以放心提交。这套流程看起来繁琐但它能避免90%的贪心翻车场景。尤其在算法面试里面试官更看重你展示验证过程而不是直接秒杀答案——因为秒杀答案容易让人怀疑你是不是背了题但如果你能清楚说出我尝试了A指标反例是什么所以改成B指标证明思路是什么这本身就是加分的。6.5 刷题路径建议从入门到进阶怎么安排如果你想系统练贪心我建议按照这个顺序来先从分发饼干、柠檬水找零这类一眼贪心的简单题入手建立对贪心选择的直觉。然后做区间调度、无重叠区间、用最少数量的箭引爆气球这类区间排序题掌握排序扫描的套路。接着挑战跳跃游戏、加油站这类可达性/存在性贪心锻炼维护最远覆盖范围的能力。最后再看哈夫曼编码、最小生成树这类需要额外数据结构配合的进阶题感受贪心在更复杂场景中的应用方式。顺序很重要。区间类问题是贪心里最机械化的一类套路固定、思维量适中很适合作为从理论到实践的过渡。跳跃游戏类的题目如果你能独立写出来说明你对贪心的全局最优已经有了一定理解。另外很多人学贪心时会和动态规划一起学这没毛病。但千万不要把贪心题用DP硬做也不要看到DP题就用贪心猜答案。建议在做一道题时刻意问自己这个题的局部决策会不会影响后面的决策如果会大概率需要DP如果不会才有可能用贪心。我个人在实际操作中的体验是贪心算法的学习曲线很特殊——入门极快深挖极难。你花一天就能理解什么是贪心但要花很久才能真正做到拿到新题快速判断能否贪心、怎么贪。最有效的方法是大量练习加反复思考经典题的证明而不是追求刷题数量。另外如果你在笔试或面试中遇到了不能用贪心的题目可以主动跟面试官沟通你的思考过程这样即使最终解法不对也能让对方看到你的分析能力。最后分享一个我常用的小技巧遇到拿不准的贪心题先写一个暴力解回溯或DP再用随机小数据对拍。这比看半天题解有效得多。毕竟纸上谈兵永远比不过实际跑一遍。