很多刷题的人到了贪心算法这个章节都会产生同一种错觉例题看起来都特别简单无非是每一步选个当前最优的代码还短十几行就能过。可真到自己动手做新题wa几次就懵了——明明每一步都取最大、取最小、看起来相当有道理答案就是不对。更挫败的是翻题解只有一句话“按某某排序后贪心即可”没人告诉你这句话是怎么来的。这篇“贪心算法基础II”就是想帮你把从“认识贪心题”到“能用贪心解题”之间那堵墙推倒。基础I通常教你认识什么是贪心、有哪些经典模型而这一篇更接近实战什么样的题能贪、什么样的题不能贪、证明贪心策略的常用方法、高频题型的策略归类以及我实际刷题和带人时踩过的一堆坑。阅读前提是你已经写过一些贪心题至少知道“每次选当前看起来最好的方案”这个朴素说法。不过哪怕你只学过基础I甚至只是听说过贪心算法这篇也能看因为所有推导我都会从问题本身出发。1. 为什么很多题看着像贪心却一交就wa1.1 会做模板题不等于会贪心贪心题有一个很迷惑人的表象代码短思路“直白”。活动选择、找零钱、排序后取前K个——这些模板题刷过之后人会误以为贪心就是“找最大/最小就行”。但模板题之所以是模板是因为它的最优决策已经被事先证明过你记住结论直接用就行。真实场景里题目只会给你一个从没见过的问题你要做的第一件事不是写代码而是判断“这题能不能贪”。我见过不少人刷了四五十道贪心题问他“贪心算法什么时候能用”回答还是“每一步局部最优就是全局最优”。这个说法不是错但等于没说。因为它没有给出任何可操作的判断标准。基础II要补的第一课把贪心从“记住题型”上升到“独立判断策略正确性”的层次。判断策略正确性靠的不是运气是证明至少是一套能说服自己的逻辑。1.2 局部最优与全局最优的分裂先用一个很小的例子让你体会“每一步局部最优”为什么会翻车。假设硬币面额只有三种1元、3元、4元。现在需要凑出6元要求硬币数量最少。很自然的贪心策略是“每次优先取最大面额”先拿4元剩2元拿1元再拿1元一共3枚。但最优解其实是3元3元一共2枚。贪心策略在这里失效了。“每次拿最大面额”确实是局部最优因为单看这一步面额越大越接近目标。但走到最后你会发现拿了4元之后剩余2元只能用1元补齐而最初少拿1元、拿两个3元反而更快凑满。这个例子足够说明贪心策略的本质是一个假设——假设每一步的局部最优选择能够与后续的最优选择相容。这个假设并不总是成立。1.3 基础II到底补什么既然贪心不是“无脑取最值”基础II的内容其实可以拆成三块第一正确性判断。拿到一个新题用什么方法快速验证“这个贪心策略对不对”。这是绝大多数人最缺的能力也是本文第二个章节重点展开的内容。第二策略归类。贪心虽然题目千变万化但常见的高频题型是有共性的比如区间类、覆盖类、分配类。每一类的排序键选择、贪心方向、证明套路都有迹可循。第三个章节专门做这个。第三实现与验证。贪心代码短但短代码里藏着排序键、边界条件、相等元素顺序这些细节稍不注意就wa。同时当你对某个策略没把握时怎么用对拍和随机数据快速找出反例这个我在最后一部分详细讲。2. 证明贪心正确性的三板斧贪心选择、最优子结构、交换论证2.1 第一板斧贪心选择性质贪心选择性质的定义是每一步做出的局部最优选择都存在一个全局最优解包含这个选择。翻译成人话就是你先做“当前最划算”的决定这个决定不会挡路后面再选一选依然能凑出最优结果。回到上面硬币例子。对“优先取最大面额”这个贪心策略来说每一步选的“最大面额”不存在一个全局最优解包含它——凑6元的最优解是33没有一个最优解包含4元硬币。所以这个策略不满足贪心选择性质它从一开始就没有翻身机会。验证贪心选择性质最常用的方法是反证法假设存在一个不包含贪心选择g的最优解OPT然后想办法把OPT中的某个元素替换成g并证明替换后的解依然是最优的。如果替换后不劣那么g可以进入某个最优解贪心选择性质得证。2.2 第二板斧最优子结构最优子结构是说原问题的最优解里去掉第一步之后剩下部分仍然是子问题的最优解。这个性质在动态规划里也会遇到但贪心对它的依赖更强。因为贪心是“一条道走到黑”一旦子问题不是最优前面再贪心也白搭。帮你建立一个直觉把原问题想成装修一套房子。全局最优方案是“客厅用A方案、卧室用B方案”。如果你把客厅的方案定死为A之后发现卧室在“客厅已定A”的前提下最优方案不是B而是B那原问题的“AB”就不可能是全局最优因为它没有利用子问题里的更优解。实际做题时很多问题的子问题和原问题结构完全一致比如“从i位置跳到终点”“从第i个区间开始选最多不重叠区间”这种天然的子问题结构是能用贪心/DP的前提。2.3 第三板斧交换论证法交换论证法是证明贪心正确性最硬核、最好用的一招也是很多竞赛选手口中“这题可以贪心”的真正底气。它的操作步骤很固定假设G是贪心算法给出的解OPT是某个最优解。找到G与OPT第一个产生分歧的位置。把OPT中这个位置的选择换成G中对应的贪心选择然后通过一系列交换或替换让新解OPT仍然可行并且不劣于OPT。反复执行这个替换过程最终得到结论G至少和OPT一样好。用经典的“最多不重叠区间”问题演示一遍你就能感受到这套方法的威力。题目给你一堆会议区间每场会议有开始时间start和结束时间end问最多能参加多少场不冲突的会议。贪心策略按结束时间从小到大排序优先选择结束最早且与已选会议不冲突的会议。为什么按end排序而不是按start排序用交换论证来说话。假设OPT是最优解它选择的第一个区间是i。贪心G选择的第一个区间是g。按贪心规则g是所有区间中结束最早的所以g.end i.end。现在把OPT里的第一个区间i替换成g。因为g.end i.end所以g结束得更早不会和OPT中原本排在i后面的任何区间冲突。替换之后OPT包含的区间数量不变依然是可行解而且第一个区间的结束时间被提前了。重复这个替换可以把最优先导成贪心解且数量一直不减少。因此贪心解的数量不小于最优解它就是最优解。这个逻辑链比“看着感觉很对”强一万倍。2.4 证明能力为什么直接影响过题率有人觉得竞赛、面试又不要求写证明练这个干嘛。其实证明能力不过关的直接后果就是你只能依赖“像不像见过的题”来做判断。像就套不像就瞎猜。瞎猜的后果就是wa得莫名其妙而且你甚至不知道是策略错了还是实现错了。我自己的经验是一道贪心题如果我能花十分钟把交换论证或者贪心选择性质捋通写代码通常一次过。反过来如果我只是凭直觉“试一下”起码要交两三发才可能对遇到数据强的题目试错次数可能更多。证明不是为了写进题解里当装饰是为了让你在下笔之前就确信方向没错。3. 三类高频贪心题型的策略拆解3.1 区间问题排序键决定胜负区间类贪心题是面试和竞赛里的常客而且特别能区分“背题型”和“真懂”。同样是区间目标不同排序键就完全不同一旦排序键选错后面再怎么贪都是错。我做了一个对照表覆盖三种最常见的目标目标排序方式贪心决策最多不重叠区间按右端点升序优先选结束最早的区间最少区间覆盖大区间按左端点升序每次选能延伸最远的区间合并重叠区间按左端点升序依次扩展当前合并区间的右边界最多不重叠区间刚才已经用交换论证讲过了核心是“结束早的留着后面空间更大”。最少区间覆盖则反过来了。题目给你一个大区间[L, R]和一堆小区间要用最少的小区间把这个大区间完整覆盖。此时按结束时间排序没有意义因为你的首要任务是“从左往右推进”。正确做法是按左端点升序排序然后在所有左端点不超过当前已覆盖位置的小区间里取右端点最远的那个。每选一个已覆盖位置就向右推进一格。这个策略的意义是当前这一步要尽量让覆盖范围延得更远否则后面就需要更多区间来补。合区间则最简单按start排序后维护当前区间的maxEnd遇到重叠就扩展遇到不重叠就收一个答案。区间题的关键动作就一个想清楚“在这一步哪个候选是对未来最有利的”。未来最有利就是要选择那个给剩余问题留下最大余地的选项。3.2 覆盖与跳跃问题维护边界而不是模拟过程跳跃游戏这类题第一次接触的人容易陷入一个误区去模拟“每一步该跳到哪里”。真正高效的贪心做法是维护“当前能到达的最远位置”根本不管具体跳到了哪个下标。题目给定数组numsnums[i]表示从下标i最多可以向前跳的步数问从下标0出发能不能跳到最后一个下标。贪心策略维护变量mostFar表示当前所有可达位置中能跳到的最远下标。遍历每个位置i如果i mostFar说明i可达就更新mostFar max(mostFar, i nums[i])。一旦mostFar n-1直接返回True。如果遍历过程中发现某个i mostFar说明这个位置已经不可达后面必然断裂返回False。代码实现def can_jump(nums): n len(nums) most_far 0 for i in range(n): if i most_far: return False most_far max(most_far, i nums[i]) if most_far n - 1: return True return False“维护边界而不是模拟过程”这件事本质上是一个问题的两种建模方式。模拟式思考被“我具体站在哪”绑住了而维护边界式思考只关心“我最多能覆盖到哪里”。贪心往往需要你跳出来关注状态的上界而不是状态本身。这个思路的进阶版是“最少跳跃次数”问题。此时除了维护当前步数能到达的最远边界curEnd还要维护下一步能到达的最远边界nextFar。遍历位置时不断更新nextFar当i走到curEnd时步数加一并把curEnd更新为nextFar。这个做法里你始终在做的一件事是用当前这一步能覆盖的区域去换取下一步更大的覆盖区域。3.3 分配与互相制约问题先满足最紧的约束分配类贪心题有一个共性存在多个被分配对象每个对象有不同的“需求”你希望用有限的资源满足尽可能多的需求。这类题最容易踩的坑就是“先满足谁都想不清楚”。举两个典型例子。第一个是分发饼干。孩子胃口值g[i]升序饼干尺寸s[j]升序要求用饼干满足尽可能多的孩子一个孩子只能分到一块尺寸不小于胃口的饼干。贪心策略是优先满足胃口最小的孩子并且用尺寸刚好够的最小饼干去满足他。为什么先满足胃口最小的因为胃口大的孩子难满足但满足任意一个孩子只能换来“数量1”既然收益一样就应该优先消耗最小胃口这个“最紧的约束”。而为什么用刚好够的饼干因为把大饼干留给后面的孩子成功率更高。这就是在同时做“代价最小化”和“收益最大化”。第二个是发糖果。假设一排孩子各有评分相邻比较要求评分更高的孩子必须比相邻孩子得到更多糖果每个人至少一颗求最少糖果总数。这道题的正确做法是两次遍历def candy(ratings): n len(ratings) res [1] * n # 从左到右只看左边邻居 for i in range(1, n): if ratings[i] ratings[i - 1]: res[i] res[i - 1] 1 # 从右到左只看右边邻居 for i in range(n - 2, -1, -1): if ratings[i] ratings[i 1]: res[i] max(res[i], res[i 1] 1) return sum(res)初看可能会问为什么从左到右扫一遍再从右到左扫一遍就能得到最优解因为题目约束包含两个方向“比左邻居高”和“比右邻居高”。两个方向同时约束很难一眼看穿全局。但如果把约束拆开第一遍只保证“每个孩子比左邻居高时糖果比左邻居多”第二遍只保证“每个孩子比右邻居高时糖果比右邻居多”。最后对两个方向的临时答案取max两边约束就同时满足了。这个“拆解约束取max合并”的思路本身就是解决互相制约问题的一把钥匙。它比动态规划实现简单得多而且不用证明复杂的全局性质只要证明两个方向的约束可以独立处理即可。4. 实现一套可复用的贪心代码套路4.1 贪心题的通用骨架很多贪心题虽然题面五花八门但代码骨架高度一致就四步排序或者用堆维护有序性制定一个“当前最优”的判定条件顺序遍历所有候选元素维护用于表示当前局部解的若干变量并更新答案以区间调度为例对应关系非常直观按end排序是第一步s last_end是第二步for循环是第三步count和last_end的更新是第四步。跳跃游戏里没有排序因为它依赖数组下标顺序但“维护mostFar”和“按位置顺序遍历”完全吻合这个骨架。写代码时我建议你在注释里标出这几个阶段尤其是“当前最优判定”和“答案变量更新”这两行是bug高发区注释标清楚不容易改乱。4.2 排序键的设计一步之差天壤之别80%以上的贪心算法题都需要事先排序。排序的键怎么设计直接决定整个算法的对错。判断排序键对不对有一个小技巧构造两个元素A和B问自己“如果只能选一个先选谁对我最终的目标更有利”。把这个问题想清楚排序键基本就定了。做最多不重叠区间核心目标是“给后面留空间”所以先选结束早的按键是end升序。做最少区间覆盖核心目标是“让覆盖范围快速推进”所以在左端点满足条件的前提下选右端点最大的按键是start升序、右端点降序。做分数背包核心目标是“单位重量带来最大价值”所以按键是value/weight降序。做任务调度比如每个任务有截止时间d和收益p想最大化总收益通常会按截止时间升序再用小根堆维护已选任务的最小收益遇到超期任务就踢掉收益最小的那个。排序键背后其实是一个很朴素的想法优先处理“限制最死”“代价最小”“收益最大”的对象。你先把它排到前面后面的决策空间自然就大了。4.3 复杂度与性能为什么贪心可以比DP快同样一个问题动态规划和贪心都能解时贪心通常快一个量级。原因也简单动态规划会维护一整个状态空间每个状态都要计算转移贪心只沿着一个方向走每一步只选一个。最典型的就是“最多不重叠区间”和“加权区间调度”的区别。前者用贪心排序O(n log n)加遍历O(n)。后者每个区间带权重要的是最大权重和这时候贪心就失效了因为“结束最早”不代表“权重最大”必须动态规划按结束时间排序后二分转移复杂度是O(n log n)起步但状态和转移复杂得多。什么时候该从贪心切到DP当你发现“当前最优”并不能只看一维属性而是依赖多个变量的联合状态时。比如加权区间调度里“时间”和“权重”两个目标同时存在贪心无法同时优化两个目标DP的“考虑前i个区间”状态可以轻松表达这种组合。性能上贪心确实占优但不要为了性能强行贪心。一个需要O(n^2)的DP通常比一个错误贪心的O(n log n)更值得写。5. 实战复盘用一套完整流程解“加油站”前面讲的是方法论这一节我用一道经典题把“读题 → 猜策略 → 证明 → 实现 → 测试”完整走一遍。选的题目是加油站有n个加油站gas[i]是第i个加油站能加的油量cost[i]是从第i个站开到第i1个站需要的油量。你的车油箱一开始是空的从某个加油站出发问能不能顺时针绕一圈回到出发点如果能返回出发站下标否则返回-1。我故意选了这道题因为它足够反直觉而且很多人第一次做的时候会去猜“从净收益最大的站出发”这个方向是错的。5.1 读题识别决策变量读题先别急着想算法先找“如果我们做出选择选择的对象是什么”。这道题的选择对象是“起点”。一旦定了起点中间没有其他可决策的点因为你每到一个站加油量是固定的开往下一站的耗油也是固定的整个路线是被起点唯一确定的。这说明什么说明这个问题不是“做一串决策”而是“选一个起点”。事件一旦发现决策空间只有一维就要立刻想到线性扫描而不是二维DP或复杂搜索。5.2 猜策略一个反直觉的方向先做一个全局判断如果所有gas[i] - cost[i]的总和小于0那么油的总量都不够环线消耗肯定无解直接返回-1。当总和大于等于0时是否一定有解答案是确定的。你从任何站出发只要有一个站能作为起点就能完成一圈。而“存在性”由总油量非负保证这一点可以这样理解如果把整个环想象成不同路段的有向图总消耗不超过总供给那么至少有一个“入口路段”是能提供净正油的。接下来的问题是怎么找这个起点。一个常见的错误直觉是找gas[i] - cost[i]最大净收益最大的站作为起点。这个直觉之所以错是因为净收益最大的站可能在它绕到一半时因为某段累计消耗过大而“断油”而一个净收益没那么高但位置恰好的站反而能顺利走完。正确的贪心策略是下面这个从下标0开始按顺序累加剩余油量cur如果累加到某站i时cur小于0说明从当前尝试的起点start到i之间任何位置都不可能是合法起点直接把start设为i1并把cur清零。5.3 证明为什么“归零重置”是安全的这一段的正确性是整个算法的命门必须讲透。假设你从start出发一路加到位置i剩余油量cur第一次小于0。这意味着从start到i这一段总消耗大于总加油量。现在要证明从start到i之间的任意位置j作为起点都不可能完成一整圈。直观上想如果j在start和i之间那么从start出发到达j时车里的剩余油量一定是大于等于0的因为cur在i之前都没小于过0。换句话说从j出发相当于“继承”了start到达j时非负的初始油量。如果连“带着这些油继续从j走到i”都会断油那么“空油箱从j出发”就更不可能走完j到i这段路了。这个证明是标准的“反证前缀油量比较”它是这道题能贪心的关键。想明白这一段代码写起来就是几行根本不用犹豫。5.4 实现与边界测试代码实现如下def can_complete_circuit(gas, cost): total 0 cur 0 start 0 for i in range(len(gas)): remain gas[i] - cost[i] total remain cur remain if cur 0: start i 1 cur 0 return start if total 0 else -1边界情况主要是两类。第一类是只有一个加油站此时如果gas[0] cost[0]就返回0否则返回-1上面代码直接支持。第二类是起点重置到数组末尾之后比如start等于n说明尝试从最后一个站重新开始此时start的取模问题不需要处理因为只要total 0正确的起点一定在扫描过程中被确定下来。测试时多构造几个用例gas和cost都相等能回原点gas整体差一点不够返回-1数组很长但前半段全是负数后半段才回正验证start会不会被错误重置。这类题目的反例往往藏在“起点重置后后续累计仍然可能再次小于0”的情况里代码天然处理了但你要想过为什么不需要第二次重置后再修正start。6. 我踩过的贪心坑和反例验证法6.1 两个目标同时贪心时往往一个都保不住这是贪心题里最经典的翻车现场。当一道题同时要求你兼顾两个指标比如“总价值最大且总重量不超过限制”很多人会尝试“每次选单位价值最高”的贪心。对于分数背包这个策略是对的因为物品可以拆分你永远可以用最高单价把剩余容量塞满但对于01背包物品不可拆分这个策略会出问题。一个常见的反例背包容量10物品A重量6价值6物品B重量5价值5物品C重量5价值5。按单位价值看都一样选A后剩余4塞不下B或C总价值6但选BC总价值10。为什么失败了因为你每次只看“当前单位价值最高”没有看到“加上重量约束后剩余容量可能被浪费”这个全局事实。遇到这种多目标题第一反应不应该套贪心而是问自己这两个目标之间是否存在耦合。存在耦合优先考虑DP或搜索不存在耦合比如“重量”和“价值”可以被某个排序键统一表示再考虑贪心。6.2 比较器缺等号和相等元素乱序贪心代码短不代表没有实现陷阱。我见过最隐蔽的一类bug出在排序比较器上。在多数语言里排序比较器需要返回负数、零、正数三种结果。如果你写比较器时只处理了a和b不相等的情况而没有处理相等的情况在某些底层的排序算法下可能会出现“比较不一致”的异常轻则效率退化重则直接运行时错误。即使没报错相等元素如果与目标函数的排序冲突也会导致同一组数据在你的本地环境和评测环境里结果不同。一个更实际的细节是Python的sort是稳定排序如果想对某个键相同的数据再按第二键排可以写成sort(keylambda x: (x[0], -x[1]))不要自己写cmp函数去折腾。自己写cmp时务必保证cmp(a, b)和cmp(b, a)互为相反数否则逻辑漏洞很难查。6.3 贪心和DP的分界线状态耦合时别硬贪很多动态规划题的最初几步看起来也像贪心。比如最长递增子序列如果你从一开始就选最小的元素局部上看确实能让后续更有空间但遇到[3, 4, 5, 1, 2, 3, 4]这类数据时贪心会先选3再选4再选5然后卡住而实际最长递增子序列是1, 2, 3, 4长度4比3更长。你每一步选的“当前最小可用”确实是最优的但选择哪个元素进入候选子序列会影响后续所有选择这就是状态耦合。判断一道题到底是贪心还是DP我常用一个土办法把问题规模缩小到两三个元素尝试手动执行“贪心选择”看这个选择是否必然出现在某个最优解里。如果它出现了放心贪如果你能找到一种情况最优解不包含这个“当前最优选择”那就说明当前最优不是一个“安全”的选择后面得靠枚举或状态转移兜底。6.4 用随机对拍守住最后一道防线就算你把上面的证明和判断都做了实现时还是可能出错。我也翻过车策略想得清清楚楚代码却因为一个边界条件写错交上去wa了三次。这时候最有效的手段不是人肉盯代码而是写个暴力解法做对拍。具体做法很简单写一个保证正确的暴力版本比如指数级枚举或DP版本再写一个要验证的贪心版本然后用随机生成的小数据同时跑两个版本一旦结果不一致立刻打印这组数据。小数据规模设置成n在1到8之间值域随机这样暴力版本也能在毫秒级跑完。import random def greedy_solve(nums): # 你的贪心实现 pass def brute_solve(nums): # 暴力枚举或DP版本 pass for _ in range(10000): n random.randint(1, 8) nums [random.randint(1, 20) for _ in range(n)] g greedy_solve(nums) b brute_solve(nums) if g ! b: print(counter example:, nums) break else: print(all tests passed)我自己的习惯是遇到没有把握的贪心题先花五分钟写暴力再跑一万组随机数据。这一招帮我挡下了至少十次无谓的wa。它的本质是把“证明”交给机器虽然随机测试不能证明全部正确性但能快速消灭“策略方向错误”和“实现细节错误”这两类问题。策略对不对先让数据说话。如果还觉得不放心就试着把刚才的构建反例过程反向思考一下什么样结构的数据最容易让你的贪心失效一般来说数据里要同时存在“看起来次优、但和后续决策更相容”的选项。找到这种数据几乎就等于找到了反例。说实话贪心算法是所有基础算法里最看“功夫在诗外”的一种。动态规划你把状态转移方程写对基本就稳了贪心却是策略猜错代码再漂亮也白搭。所以我不太迷信“多刷题自然有感觉”这句话更推荐每次写完贪心题都追问自己一个为什么——为什么这个贪心选择是安全的只要你能用反证或者交换论证把这个问题讲清楚下次见到同类问题就不再是碰运气而是真正有把握地往下写代码。
贪心算法进阶：正确性证明、高频题型与避坑指南
很多刷题的人到了贪心算法这个章节都会产生同一种错觉例题看起来都特别简单无非是每一步选个当前最优的代码还短十几行就能过。可真到自己动手做新题wa几次就懵了——明明每一步都取最大、取最小、看起来相当有道理答案就是不对。更挫败的是翻题解只有一句话“按某某排序后贪心即可”没人告诉你这句话是怎么来的。这篇“贪心算法基础II”就是想帮你把从“认识贪心题”到“能用贪心解题”之间那堵墙推倒。基础I通常教你认识什么是贪心、有哪些经典模型而这一篇更接近实战什么样的题能贪、什么样的题不能贪、证明贪心策略的常用方法、高频题型的策略归类以及我实际刷题和带人时踩过的一堆坑。阅读前提是你已经写过一些贪心题至少知道“每次选当前看起来最好的方案”这个朴素说法。不过哪怕你只学过基础I甚至只是听说过贪心算法这篇也能看因为所有推导我都会从问题本身出发。1. 为什么很多题看着像贪心却一交就wa1.1 会做模板题不等于会贪心贪心题有一个很迷惑人的表象代码短思路“直白”。活动选择、找零钱、排序后取前K个——这些模板题刷过之后人会误以为贪心就是“找最大/最小就行”。但模板题之所以是模板是因为它的最优决策已经被事先证明过你记住结论直接用就行。真实场景里题目只会给你一个从没见过的问题你要做的第一件事不是写代码而是判断“这题能不能贪”。我见过不少人刷了四五十道贪心题问他“贪心算法什么时候能用”回答还是“每一步局部最优就是全局最优”。这个说法不是错但等于没说。因为它没有给出任何可操作的判断标准。基础II要补的第一课把贪心从“记住题型”上升到“独立判断策略正确性”的层次。判断策略正确性靠的不是运气是证明至少是一套能说服自己的逻辑。1.2 局部最优与全局最优的分裂先用一个很小的例子让你体会“每一步局部最优”为什么会翻车。假设硬币面额只有三种1元、3元、4元。现在需要凑出6元要求硬币数量最少。很自然的贪心策略是“每次优先取最大面额”先拿4元剩2元拿1元再拿1元一共3枚。但最优解其实是3元3元一共2枚。贪心策略在这里失效了。“每次拿最大面额”确实是局部最优因为单看这一步面额越大越接近目标。但走到最后你会发现拿了4元之后剩余2元只能用1元补齐而最初少拿1元、拿两个3元反而更快凑满。这个例子足够说明贪心策略的本质是一个假设——假设每一步的局部最优选择能够与后续的最优选择相容。这个假设并不总是成立。1.3 基础II到底补什么既然贪心不是“无脑取最值”基础II的内容其实可以拆成三块第一正确性判断。拿到一个新题用什么方法快速验证“这个贪心策略对不对”。这是绝大多数人最缺的能力也是本文第二个章节重点展开的内容。第二策略归类。贪心虽然题目千变万化但常见的高频题型是有共性的比如区间类、覆盖类、分配类。每一类的排序键选择、贪心方向、证明套路都有迹可循。第三个章节专门做这个。第三实现与验证。贪心代码短但短代码里藏着排序键、边界条件、相等元素顺序这些细节稍不注意就wa。同时当你对某个策略没把握时怎么用对拍和随机数据快速找出反例这个我在最后一部分详细讲。2. 证明贪心正确性的三板斧贪心选择、最优子结构、交换论证2.1 第一板斧贪心选择性质贪心选择性质的定义是每一步做出的局部最优选择都存在一个全局最优解包含这个选择。翻译成人话就是你先做“当前最划算”的决定这个决定不会挡路后面再选一选依然能凑出最优结果。回到上面硬币例子。对“优先取最大面额”这个贪心策略来说每一步选的“最大面额”不存在一个全局最优解包含它——凑6元的最优解是33没有一个最优解包含4元硬币。所以这个策略不满足贪心选择性质它从一开始就没有翻身机会。验证贪心选择性质最常用的方法是反证法假设存在一个不包含贪心选择g的最优解OPT然后想办法把OPT中的某个元素替换成g并证明替换后的解依然是最优的。如果替换后不劣那么g可以进入某个最优解贪心选择性质得证。2.2 第二板斧最优子结构最优子结构是说原问题的最优解里去掉第一步之后剩下部分仍然是子问题的最优解。这个性质在动态规划里也会遇到但贪心对它的依赖更强。因为贪心是“一条道走到黑”一旦子问题不是最优前面再贪心也白搭。帮你建立一个直觉把原问题想成装修一套房子。全局最优方案是“客厅用A方案、卧室用B方案”。如果你把客厅的方案定死为A之后发现卧室在“客厅已定A”的前提下最优方案不是B而是B那原问题的“AB”就不可能是全局最优因为它没有利用子问题里的更优解。实际做题时很多问题的子问题和原问题结构完全一致比如“从i位置跳到终点”“从第i个区间开始选最多不重叠区间”这种天然的子问题结构是能用贪心/DP的前提。2.3 第三板斧交换论证法交换论证法是证明贪心正确性最硬核、最好用的一招也是很多竞赛选手口中“这题可以贪心”的真正底气。它的操作步骤很固定假设G是贪心算法给出的解OPT是某个最优解。找到G与OPT第一个产生分歧的位置。把OPT中这个位置的选择换成G中对应的贪心选择然后通过一系列交换或替换让新解OPT仍然可行并且不劣于OPT。反复执行这个替换过程最终得到结论G至少和OPT一样好。用经典的“最多不重叠区间”问题演示一遍你就能感受到这套方法的威力。题目给你一堆会议区间每场会议有开始时间start和结束时间end问最多能参加多少场不冲突的会议。贪心策略按结束时间从小到大排序优先选择结束最早且与已选会议不冲突的会议。为什么按end排序而不是按start排序用交换论证来说话。假设OPT是最优解它选择的第一个区间是i。贪心G选择的第一个区间是g。按贪心规则g是所有区间中结束最早的所以g.end i.end。现在把OPT里的第一个区间i替换成g。因为g.end i.end所以g结束得更早不会和OPT中原本排在i后面的任何区间冲突。替换之后OPT包含的区间数量不变依然是可行解而且第一个区间的结束时间被提前了。重复这个替换可以把最优先导成贪心解且数量一直不减少。因此贪心解的数量不小于最优解它就是最优解。这个逻辑链比“看着感觉很对”强一万倍。2.4 证明能力为什么直接影响过题率有人觉得竞赛、面试又不要求写证明练这个干嘛。其实证明能力不过关的直接后果就是你只能依赖“像不像见过的题”来做判断。像就套不像就瞎猜。瞎猜的后果就是wa得莫名其妙而且你甚至不知道是策略错了还是实现错了。我自己的经验是一道贪心题如果我能花十分钟把交换论证或者贪心选择性质捋通写代码通常一次过。反过来如果我只是凭直觉“试一下”起码要交两三发才可能对遇到数据强的题目试错次数可能更多。证明不是为了写进题解里当装饰是为了让你在下笔之前就确信方向没错。3. 三类高频贪心题型的策略拆解3.1 区间问题排序键决定胜负区间类贪心题是面试和竞赛里的常客而且特别能区分“背题型”和“真懂”。同样是区间目标不同排序键就完全不同一旦排序键选错后面再怎么贪都是错。我做了一个对照表覆盖三种最常见的目标目标排序方式贪心决策最多不重叠区间按右端点升序优先选结束最早的区间最少区间覆盖大区间按左端点升序每次选能延伸最远的区间合并重叠区间按左端点升序依次扩展当前合并区间的右边界最多不重叠区间刚才已经用交换论证讲过了核心是“结束早的留着后面空间更大”。最少区间覆盖则反过来了。题目给你一个大区间[L, R]和一堆小区间要用最少的小区间把这个大区间完整覆盖。此时按结束时间排序没有意义因为你的首要任务是“从左往右推进”。正确做法是按左端点升序排序然后在所有左端点不超过当前已覆盖位置的小区间里取右端点最远的那个。每选一个已覆盖位置就向右推进一格。这个策略的意义是当前这一步要尽量让覆盖范围延得更远否则后面就需要更多区间来补。合区间则最简单按start排序后维护当前区间的maxEnd遇到重叠就扩展遇到不重叠就收一个答案。区间题的关键动作就一个想清楚“在这一步哪个候选是对未来最有利的”。未来最有利就是要选择那个给剩余问题留下最大余地的选项。3.2 覆盖与跳跃问题维护边界而不是模拟过程跳跃游戏这类题第一次接触的人容易陷入一个误区去模拟“每一步该跳到哪里”。真正高效的贪心做法是维护“当前能到达的最远位置”根本不管具体跳到了哪个下标。题目给定数组numsnums[i]表示从下标i最多可以向前跳的步数问从下标0出发能不能跳到最后一个下标。贪心策略维护变量mostFar表示当前所有可达位置中能跳到的最远下标。遍历每个位置i如果i mostFar说明i可达就更新mostFar max(mostFar, i nums[i])。一旦mostFar n-1直接返回True。如果遍历过程中发现某个i mostFar说明这个位置已经不可达后面必然断裂返回False。代码实现def can_jump(nums): n len(nums) most_far 0 for i in range(n): if i most_far: return False most_far max(most_far, i nums[i]) if most_far n - 1: return True return False“维护边界而不是模拟过程”这件事本质上是一个问题的两种建模方式。模拟式思考被“我具体站在哪”绑住了而维护边界式思考只关心“我最多能覆盖到哪里”。贪心往往需要你跳出来关注状态的上界而不是状态本身。这个思路的进阶版是“最少跳跃次数”问题。此时除了维护当前步数能到达的最远边界curEnd还要维护下一步能到达的最远边界nextFar。遍历位置时不断更新nextFar当i走到curEnd时步数加一并把curEnd更新为nextFar。这个做法里你始终在做的一件事是用当前这一步能覆盖的区域去换取下一步更大的覆盖区域。3.3 分配与互相制约问题先满足最紧的约束分配类贪心题有一个共性存在多个被分配对象每个对象有不同的“需求”你希望用有限的资源满足尽可能多的需求。这类题最容易踩的坑就是“先满足谁都想不清楚”。举两个典型例子。第一个是分发饼干。孩子胃口值g[i]升序饼干尺寸s[j]升序要求用饼干满足尽可能多的孩子一个孩子只能分到一块尺寸不小于胃口的饼干。贪心策略是优先满足胃口最小的孩子并且用尺寸刚好够的最小饼干去满足他。为什么先满足胃口最小的因为胃口大的孩子难满足但满足任意一个孩子只能换来“数量1”既然收益一样就应该优先消耗最小胃口这个“最紧的约束”。而为什么用刚好够的饼干因为把大饼干留给后面的孩子成功率更高。这就是在同时做“代价最小化”和“收益最大化”。第二个是发糖果。假设一排孩子各有评分相邻比较要求评分更高的孩子必须比相邻孩子得到更多糖果每个人至少一颗求最少糖果总数。这道题的正确做法是两次遍历def candy(ratings): n len(ratings) res [1] * n # 从左到右只看左边邻居 for i in range(1, n): if ratings[i] ratings[i - 1]: res[i] res[i - 1] 1 # 从右到左只看右边邻居 for i in range(n - 2, -1, -1): if ratings[i] ratings[i 1]: res[i] max(res[i], res[i 1] 1) return sum(res)初看可能会问为什么从左到右扫一遍再从右到左扫一遍就能得到最优解因为题目约束包含两个方向“比左邻居高”和“比右邻居高”。两个方向同时约束很难一眼看穿全局。但如果把约束拆开第一遍只保证“每个孩子比左邻居高时糖果比左邻居多”第二遍只保证“每个孩子比右邻居高时糖果比右邻居多”。最后对两个方向的临时答案取max两边约束就同时满足了。这个“拆解约束取max合并”的思路本身就是解决互相制约问题的一把钥匙。它比动态规划实现简单得多而且不用证明复杂的全局性质只要证明两个方向的约束可以独立处理即可。4. 实现一套可复用的贪心代码套路4.1 贪心题的通用骨架很多贪心题虽然题面五花八门但代码骨架高度一致就四步排序或者用堆维护有序性制定一个“当前最优”的判定条件顺序遍历所有候选元素维护用于表示当前局部解的若干变量并更新答案以区间调度为例对应关系非常直观按end排序是第一步s last_end是第二步for循环是第三步count和last_end的更新是第四步。跳跃游戏里没有排序因为它依赖数组下标顺序但“维护mostFar”和“按位置顺序遍历”完全吻合这个骨架。写代码时我建议你在注释里标出这几个阶段尤其是“当前最优判定”和“答案变量更新”这两行是bug高发区注释标清楚不容易改乱。4.2 排序键的设计一步之差天壤之别80%以上的贪心算法题都需要事先排序。排序的键怎么设计直接决定整个算法的对错。判断排序键对不对有一个小技巧构造两个元素A和B问自己“如果只能选一个先选谁对我最终的目标更有利”。把这个问题想清楚排序键基本就定了。做最多不重叠区间核心目标是“给后面留空间”所以先选结束早的按键是end升序。做最少区间覆盖核心目标是“让覆盖范围快速推进”所以在左端点满足条件的前提下选右端点最大的按键是start升序、右端点降序。做分数背包核心目标是“单位重量带来最大价值”所以按键是value/weight降序。做任务调度比如每个任务有截止时间d和收益p想最大化总收益通常会按截止时间升序再用小根堆维护已选任务的最小收益遇到超期任务就踢掉收益最小的那个。排序键背后其实是一个很朴素的想法优先处理“限制最死”“代价最小”“收益最大”的对象。你先把它排到前面后面的决策空间自然就大了。4.3 复杂度与性能为什么贪心可以比DP快同样一个问题动态规划和贪心都能解时贪心通常快一个量级。原因也简单动态规划会维护一整个状态空间每个状态都要计算转移贪心只沿着一个方向走每一步只选一个。最典型的就是“最多不重叠区间”和“加权区间调度”的区别。前者用贪心排序O(n log n)加遍历O(n)。后者每个区间带权重要的是最大权重和这时候贪心就失效了因为“结束最早”不代表“权重最大”必须动态规划按结束时间排序后二分转移复杂度是O(n log n)起步但状态和转移复杂得多。什么时候该从贪心切到DP当你发现“当前最优”并不能只看一维属性而是依赖多个变量的联合状态时。比如加权区间调度里“时间”和“权重”两个目标同时存在贪心无法同时优化两个目标DP的“考虑前i个区间”状态可以轻松表达这种组合。性能上贪心确实占优但不要为了性能强行贪心。一个需要O(n^2)的DP通常比一个错误贪心的O(n log n)更值得写。5. 实战复盘用一套完整流程解“加油站”前面讲的是方法论这一节我用一道经典题把“读题 → 猜策略 → 证明 → 实现 → 测试”完整走一遍。选的题目是加油站有n个加油站gas[i]是第i个加油站能加的油量cost[i]是从第i个站开到第i1个站需要的油量。你的车油箱一开始是空的从某个加油站出发问能不能顺时针绕一圈回到出发点如果能返回出发站下标否则返回-1。我故意选了这道题因为它足够反直觉而且很多人第一次做的时候会去猜“从净收益最大的站出发”这个方向是错的。5.1 读题识别决策变量读题先别急着想算法先找“如果我们做出选择选择的对象是什么”。这道题的选择对象是“起点”。一旦定了起点中间没有其他可决策的点因为你每到一个站加油量是固定的开往下一站的耗油也是固定的整个路线是被起点唯一确定的。这说明什么说明这个问题不是“做一串决策”而是“选一个起点”。事件一旦发现决策空间只有一维就要立刻想到线性扫描而不是二维DP或复杂搜索。5.2 猜策略一个反直觉的方向先做一个全局判断如果所有gas[i] - cost[i]的总和小于0那么油的总量都不够环线消耗肯定无解直接返回-1。当总和大于等于0时是否一定有解答案是确定的。你从任何站出发只要有一个站能作为起点就能完成一圈。而“存在性”由总油量非负保证这一点可以这样理解如果把整个环想象成不同路段的有向图总消耗不超过总供给那么至少有一个“入口路段”是能提供净正油的。接下来的问题是怎么找这个起点。一个常见的错误直觉是找gas[i] - cost[i]最大净收益最大的站作为起点。这个直觉之所以错是因为净收益最大的站可能在它绕到一半时因为某段累计消耗过大而“断油”而一个净收益没那么高但位置恰好的站反而能顺利走完。正确的贪心策略是下面这个从下标0开始按顺序累加剩余油量cur如果累加到某站i时cur小于0说明从当前尝试的起点start到i之间任何位置都不可能是合法起点直接把start设为i1并把cur清零。5.3 证明为什么“归零重置”是安全的这一段的正确性是整个算法的命门必须讲透。假设你从start出发一路加到位置i剩余油量cur第一次小于0。这意味着从start到i这一段总消耗大于总加油量。现在要证明从start到i之间的任意位置j作为起点都不可能完成一整圈。直观上想如果j在start和i之间那么从start出发到达j时车里的剩余油量一定是大于等于0的因为cur在i之前都没小于过0。换句话说从j出发相当于“继承”了start到达j时非负的初始油量。如果连“带着这些油继续从j走到i”都会断油那么“空油箱从j出发”就更不可能走完j到i这段路了。这个证明是标准的“反证前缀油量比较”它是这道题能贪心的关键。想明白这一段代码写起来就是几行根本不用犹豫。5.4 实现与边界测试代码实现如下def can_complete_circuit(gas, cost): total 0 cur 0 start 0 for i in range(len(gas)): remain gas[i] - cost[i] total remain cur remain if cur 0: start i 1 cur 0 return start if total 0 else -1边界情况主要是两类。第一类是只有一个加油站此时如果gas[0] cost[0]就返回0否则返回-1上面代码直接支持。第二类是起点重置到数组末尾之后比如start等于n说明尝试从最后一个站重新开始此时start的取模问题不需要处理因为只要total 0正确的起点一定在扫描过程中被确定下来。测试时多构造几个用例gas和cost都相等能回原点gas整体差一点不够返回-1数组很长但前半段全是负数后半段才回正验证start会不会被错误重置。这类题目的反例往往藏在“起点重置后后续累计仍然可能再次小于0”的情况里代码天然处理了但你要想过为什么不需要第二次重置后再修正start。6. 我踩过的贪心坑和反例验证法6.1 两个目标同时贪心时往往一个都保不住这是贪心题里最经典的翻车现场。当一道题同时要求你兼顾两个指标比如“总价值最大且总重量不超过限制”很多人会尝试“每次选单位价值最高”的贪心。对于分数背包这个策略是对的因为物品可以拆分你永远可以用最高单价把剩余容量塞满但对于01背包物品不可拆分这个策略会出问题。一个常见的反例背包容量10物品A重量6价值6物品B重量5价值5物品C重量5价值5。按单位价值看都一样选A后剩余4塞不下B或C总价值6但选BC总价值10。为什么失败了因为你每次只看“当前单位价值最高”没有看到“加上重量约束后剩余容量可能被浪费”这个全局事实。遇到这种多目标题第一反应不应该套贪心而是问自己这两个目标之间是否存在耦合。存在耦合优先考虑DP或搜索不存在耦合比如“重量”和“价值”可以被某个排序键统一表示再考虑贪心。6.2 比较器缺等号和相等元素乱序贪心代码短不代表没有实现陷阱。我见过最隐蔽的一类bug出在排序比较器上。在多数语言里排序比较器需要返回负数、零、正数三种结果。如果你写比较器时只处理了a和b不相等的情况而没有处理相等的情况在某些底层的排序算法下可能会出现“比较不一致”的异常轻则效率退化重则直接运行时错误。即使没报错相等元素如果与目标函数的排序冲突也会导致同一组数据在你的本地环境和评测环境里结果不同。一个更实际的细节是Python的sort是稳定排序如果想对某个键相同的数据再按第二键排可以写成sort(keylambda x: (x[0], -x[1]))不要自己写cmp函数去折腾。自己写cmp时务必保证cmp(a, b)和cmp(b, a)互为相反数否则逻辑漏洞很难查。6.3 贪心和DP的分界线状态耦合时别硬贪很多动态规划题的最初几步看起来也像贪心。比如最长递增子序列如果你从一开始就选最小的元素局部上看确实能让后续更有空间但遇到[3, 4, 5, 1, 2, 3, 4]这类数据时贪心会先选3再选4再选5然后卡住而实际最长递增子序列是1, 2, 3, 4长度4比3更长。你每一步选的“当前最小可用”确实是最优的但选择哪个元素进入候选子序列会影响后续所有选择这就是状态耦合。判断一道题到底是贪心还是DP我常用一个土办法把问题规模缩小到两三个元素尝试手动执行“贪心选择”看这个选择是否必然出现在某个最优解里。如果它出现了放心贪如果你能找到一种情况最优解不包含这个“当前最优选择”那就说明当前最优不是一个“安全”的选择后面得靠枚举或状态转移兜底。6.4 用随机对拍守住最后一道防线就算你把上面的证明和判断都做了实现时还是可能出错。我也翻过车策略想得清清楚楚代码却因为一个边界条件写错交上去wa了三次。这时候最有效的手段不是人肉盯代码而是写个暴力解法做对拍。具体做法很简单写一个保证正确的暴力版本比如指数级枚举或DP版本再写一个要验证的贪心版本然后用随机生成的小数据同时跑两个版本一旦结果不一致立刻打印这组数据。小数据规模设置成n在1到8之间值域随机这样暴力版本也能在毫秒级跑完。import random def greedy_solve(nums): # 你的贪心实现 pass def brute_solve(nums): # 暴力枚举或DP版本 pass for _ in range(10000): n random.randint(1, 8) nums [random.randint(1, 20) for _ in range(n)] g greedy_solve(nums) b brute_solve(nums) if g ! b: print(counter example:, nums) break else: print(all tests passed)我自己的习惯是遇到没有把握的贪心题先花五分钟写暴力再跑一万组随机数据。这一招帮我挡下了至少十次无谓的wa。它的本质是把“证明”交给机器虽然随机测试不能证明全部正确性但能快速消灭“策略方向错误”和“实现细节错误”这两类问题。策略对不对先让数据说话。如果还觉得不放心就试着把刚才的构建反例过程反向思考一下什么样结构的数据最容易让你的贪心失效一般来说数据里要同时存在“看起来次优、但和后续决策更相容”的选项。找到这种数据几乎就等于找到了反例。说实话贪心算法是所有基础算法里最看“功夫在诗外”的一种。动态规划你把状态转移方程写对基本就稳了贪心却是策略猜错代码再漂亮也白搭。所以我不太迷信“多刷题自然有感觉”这句话更推荐每次写完贪心题都追问自己一个为什么——为什么这个贪心选择是安全的只要你能用反证或者交换论证把这个问题讲清楚下次见到同类问题就不再是碰运气而是真正有把握地往下写代码。