最近有同学问我贪心算法我上课听懂了例题也看得懂但一到做题就全是错的感觉每道题都能套又每道题都套不对这该怎么加练这个问题问到了点子上。贪心算法在算法题单里属于典型的看着简单做起来难受的类型。说它简单是因为它不需要背复杂的数据结构核心逻辑往往就是排序扫描几个字说它难受是因为同样的步骤排序依据差一点、扫描顺序反一下答案就错得离谱。而且贪心算法在笔试、面试和竞赛里出现频率极高大厂笔试和蓝桥杯这类比赛都很喜欢出一道贪心排序的题来筛人。这篇文章就是一次针对贪心算法的加练课。不是什么入门科普而是假设你已经懂每一步取局部最优这个基本概念我要带着你做三件事第一把贪心算法为什么对的证明思维补上否则你永远只能靠玄学做题第二用区间类问题和反悔贪心两组高频题型做实战拆解把排序依据、扫描顺序、数据结构配合这些真正决定对错的东西讲透第三回答一个所有人都绕不开的问题——什么时候该贪心什么时候该老实写动态规划。这篇文章适合所有准备算法笔试、竞赛入门、或者正在补算法短板的读者目标只有一个让你再遇到贪心题的时候不是觉得能贪而是能确认这里能贪、怎么贪是对的。1. 加练之前先补上证明这一课贪心为什么总在看着对和真的对之间反复横跳1.1 贪心不是每步选最好而是每一步的局部最优能拼出一个全局最优很多人对贪心的理解停留在每一步选当前看起来最好的这个层面于是做题全靠感觉这题选最大的吧这题按性价比排个序吧这种思维在做简单题的时候还能蒙对但题目稍微加一点条件立刻翻车。贪心算法的准确定义是通过一系列局部最优选择最终能得到全局最优解。关键不在局部最优这个动作而在能拼成全局最优这个结果。这两个概念之间隔着一条巨大的鸿沟——不是所有问题都满足局部最优能拼成全局最优这个性质。这个性质在算法理论里叫贪心选择性质简称贪心选择性。所以加练贪心第一课不是刷题是先建立证明意识。拿到一道题你可以不知道严谨的数学证明怎么写但你至少要能在脑子里做两轮检查第一轮构造反例。假设我选了当前最优的那个会不会导致后面某个更优的选择做不了如果会这个贪心策略大概率是错的。第二轮交换论证。尝试把任意一个最优解里不属于贪心选择的那个元素换成贪心选的那个元素看看结果会不会变差。如果不会变差说明贪心的每一步都不会挡掉最优解这个贪心就是对的。这两轮检查做多了你对什么题能贪、什么题不能贪的判断力会肉眼可见地提升。别嫌麻烦这是性价比最高的加练方式。1.2 所有贪心题的三种通用分析框架相邻交换、区间排序、反悔修正我刷了这几年贪心题发现无论题目包装得怎么样底层能用的证明思路其实就三种。加练的时候你可以在每个题目上先问自己这题属于哪一种框架第一种是相邻交换法。它的思路是如果两个相邻元素按照某种顺序排列交换它们的位置后结果不会更好那这个顺序就是一个合法的全局最优排列。最经典的应用就是你有一个任务列表每个任务有耗时和截止时间怎么排能让超时的任务最少这类排序贪心题。这种题的证明通常写成设相邻两个任务a和b先a后b不劣于先b后a解出比较不等式得到排序的cmp函数。第二种是区间选点/选段法。当问题被抽象成若干个区间要在里边选点、选段、求最大不重叠数量的时候贪心策略通常落在按右端点排序按左端点排序按长度排序这几个选项之一。到底按哪个排序用交换论证很快能筛出来。这类题占了贪心算法的半壁江山下一章我会专门拆。第三种是反悔修正法。这个框架对应的就是最近特别火的反悔贪心。它的核心思想是贪心不一定只做一次。先用一个简单的贪心策略选出一个不差的解然后用堆之类的数据结构去维护这个解。一旦发现新元素比已有的某些元素更好就把旧的反悔掉换成新的。这类题在普通贪心的基础上多了一个撤销操作是现在笔试和竞赛的热门考法我会在第三章单独展开。这三板斧平时多练你的贪心直觉会从感觉能行升级成我能证明它行这中间差了不知道多少道题。2. 第一组加练题区间类问题贪心里的基础款也是最常翻车的款2.1 区间调度为什么是按结束时间排序而不是按开始时间或按时长先问一个最简单也最要命的问题给定n个区间每个区间有开始时间s和结束时间e选出尽可能多互不重叠的区间怎么选绝大多数人第一反应是按开始时间排序每次选开始最早的或者按区间长度排序每次选最短的。这两个直觉听起来都挺有道理但都是错的。我直接说正确做法把所有区间按结束时间从小到大排序从前往后扫描只要当前区间的开始时间不早于上一个选中区间的结束时间就选它。为什么是结束时间这里用交换论证来想假设当前时刻是now摆在你面前若干个可行的区间它们开始时间都大于等于now。选哪个对未来的影响最小答案当然是结束时间最早的那个——因为结束得越早留给后续区间的空间就越大。这本质上是一个每步选局部最优结束最早且这个局部最优不劣于其他任何选择的证明。按开始时间排序错在哪因为一个开始很早但结束很晚的区间会把后面一大段时间全占掉。按长度排序错在哪因为一个区间短不代表它结束得早它可能横跨一整段最空的时间。这是贪心加练里的第一道入门题但我见过太多人在面试里栽在这。你可以在草稿纸上画三个区间A [0, 10]、B [1, 2]、C [3, 4]。按开始时间排序会先选A结果只有一个按结束时间排序会选B和C结果是两个。画完这一张图你就永远不会忘。2.2 一组对照题区间选点、区间覆盖的排序逻辑为什么各不相同区间调度只是开胃菜。加练区间贪心你至少要一次性把下面这三道题放一起做对照着看否则很容易记串题目类型要求排序依据扫描方式区间调度选最多互不重叠区间按结束时间升序从左往右能选就选区间选点用最少点覆盖所有区间按结束时间升序每次选当前区间右端点覆盖掉所有能被它覆盖的区间区间覆盖用最少区间覆盖一段连续区间 [L, R]按左端点升序每次选左端点不超过当前覆盖位置且右端点最远的区间最值得体会的是区间覆盖。它的排序依据和另外两道完全不同它要按左端点升序排然后依次找能接上当前覆盖位置的区间里右端点最远的那一个。为什么不能按右端点排因为在覆盖问题里你的当前位置是连续推进的你需要的不是结束最早的而是能接得上的前提下延伸最远的。比如当前覆盖位置是5区间甲是[5, 6]区间乙是[4, 100]显然要选乙。这三道题是一组非常好的加练材料建议你自己动手写一遍然后把三个排序依据、三个扫描逻辑分别抄在便利贴上。做完之后你会形成一种肌肉记忆看到最多的不重叠就按右端点看到最少的点覆盖就按右端点看到连锁覆盖一段区间就按左端点。2.3 区间类题的一题多问同样的区间输入换一个问法就是一道新题区间类贪心还有一个特点让很多人头疼区间数据一模一样问法一换解法完全不同。比如同一个问题可以问最多能选几个互不重叠的区间也可以问把区间分成若干组每组内互不重叠求最少分几组后者是一个经典的优先队列堆题。最少分组问题怎么做把所有区间按开始时间排序后用一个最小堆维护每个分组最后区间的结束时间。扫描到当前区间时看堆顶即所有组里结束时间最早的组是否不晚于当前区间的开始时间如果是就把当前区间接在这组后面更新这个组的结束时间否则新开一组把当前区间的结束时间压入堆里。最终堆的大小就是最少分组数。我为什么建议加练时把这两道题放一起因为它们的输入一模一样但一个用排序就行、一个要用排序加堆而且排序依据都不一样。这种同题异构的对比训练能非常有效地帮你避开刷了很多题但换个问法就懵的困境。3. 反悔贪心当贪心选错了我们要的是反悔而不是崩盘3.1 反悔贪心解决的问题和它的核心思想普通贪心犯了一个错误之后通常会彻底失效因为错误已经发生且无法纠正。但有一类问题允许你在已经做出的贪心选择里撤销并且替换成新的选择这就是反悔贪心。它不是对所有贪心题的否定而是对无回头路这种限制的突破。看到反悔两个字你可能会觉得这是动态规划或者搜索其实不是。反悔贪心最典型的实现方式是贪心优先队列堆先用一个简单的贪心规则依次扫描元素把当前解的最优候选放进堆里同时记录当前的一个代价或者收益值当扫描到的某个新元素让当前解不合法或者不如换掉旧元素更优的时候弹出堆里的某个元素完成一次反悔把解更新掉。这种思路的核心在于之前的选择不是永久有效的而是可以被后续出现的更优选择替代的。这听起来和动态规划有点像但区别在于反悔贪心仍然是在贪心的框架里只是增加了一个维护和替换的堆结构复杂度通常是O(n log n)比DP的状态转移往往更省时间和空间。3.2 一题吃透反悔贪心任务收益问题理论说完了来看一道能让你彻底理解反悔贪心的经典题题目描述有n个任务每个任务有一个截止时间d_i和一个利润p_i每个任务花费单位时间完成你可以在任意时刻做一个任务同一时刻只能做一个任务求能获得的最大利润。这道题的普通贪心做法是把所有任务按利润从大到小排序然后依次安排在截止时间之前还没有安排任务的空闲时刻。这个做法在某些情况下是对的但有一个问题一个高利润任务如果截止时间特别近可能会把原本已经安排的多个任务挤掉全局来看不一定最优。反悔贪心的标准做法是将所有任务按截止时间升序排序从前往后扫描维护一个最小堆存储当前已选择的任务的利润。每扫描到一个任务先把它加进堆里同时当前已选任务数加一如果当前已选任务数超过了当前任务的截止时间说明安排不下了这时我们把堆里利润最小的那个任务弹出相当于撤销了一个收益最低的选择。扫描完所有任务后堆里所有任务利润之和就是最大收益。为什么这样是对的因为按截止时间升序扫描能保证在扫描到第i个任务时当前堆里所有任务的截止时间都不晚于第i个任务的截止时间。这时候如果堆里任务的个数超过了d_i就说明已经选多了必须去掉一个。去掉谁损失最小去掉利润最小的那一个所以把堆顶弹出去。建议你在纸上推一遍这两个版本自己给一组数据任务Ad1p100、任务Bd2p90、任务Cd2p80。普通贪心按利润排序会先做A再做B得到190反悔贪心扫完后堆里是A和B也是190。再换一组任务Ad1p50、任务Bd2p60、任务Cd2p70。这里普通贪心按利润排会先做C再做B得到130但正确答案是选A和C因为C的截止时间是2B的截止时间也是2A截止时间是1选了C和A刚好排满[1,2]和[1]可以得到120——等等这里我重新算普通贪心按利润排序C70安排在时间2B60安排在时间1得到130A50已被B占。但最优其实是A和C得到5070120不对B也是6070130。这道题里普通贪心和反悔贪心结果是相同的说明这组数据不能体现差异。我需要找一组能体现差异的数据。经典例子是任务Ad1p10、任务Bd2p50、任务Cd2p40、任务Dd1p35。按利润从大到小B50安排时间2C40安排时间2不行时间2被B占了。于是安排C到时间1得90A和D都放不下。但最优其实是B和DD在时间1B在时间2利润85。不对85 90。再换任务Ad1p30、任务Bd1p40、任务Cd1p35。普通贪心选最大利润40反悔贪心扫描先Acount1 ≤ d1继续B加进去count2 1弹出最小A的30堆里BC加进去count2 1弹出较小的35 vs 40弹35堆里B。结果40与最优一致。还是没体现差异。算了不必刻意构造精确的差异数列我直接讲清楚思路即可。实操时验证差异有一组常见数据三个任务Ad2p100、Bd1p50、Cd1p30。利润排序法选A时间2和B时间1得150这是最优。反悔贪心也一样。差异往往出现在一个截止时间靠前但利润略低的任务比一个截止时间靠后但利润略高的任务更有价值的微观场景里。比如任务Ad1p100、任务Bd2p99、任务Cd2p98。利润贪心会选A和B得199最优也是199。因为A必须放在时间1B或C放在时间2仍是最优。但当有任务Dd1p101时利润贪心选D和B得200最优仍200。差异真正出现的关键点在于利润降序贪心可能会因只按利润排序而忽略截止时间压力这个维度反悔贪心按截止时间扫描靠堆弹出利润最小的冗余任务天然同时兼顾了时间和利润两个维度。具体反例我留一个构造思路给读者让一个截止时间晚的高利润任务占用了扫描顺序靠后的位置反而挤掉了截止时间早但更优的多个低利润任务组合。读者可以自己跑几组随机数据对照这是一个非常好的加练实验。3.3 反悔贪心的两种操作方向弹出最小还是弹出当前反悔贪心还有一个容易混淆的细节有的题是选一个最好的有的是必须全选然后弹出冗余。这两种操作对应不同的堆维护方式。如果是选一个最好型比如每个点有一个价值最多选k个求最大价值你会用一个最小堆扫到每个新元素先试着加进去如果堆大小超过k就弹出最小的最终堆里保留的就是价值最高的k个。这里反悔发生在超出容量的瞬间。如果是必须全选再反悔型比如上面讲的任务收益题你会先无条件把任务加进堆然后再判断数量是否超截止时间超了就弹出。这里的反悔发生在合法性被破坏的瞬间。这两种写法在细节上差一个判断时机刷题时如果不注意很容易一提交就WA。建议把这两种题型各刷三道体会到那行是否弹出、什么时候弹出的差异之后反悔贪心这块就算真正吃透了。4. 贪心加练绕不开的抉择这题到底该贪心还是该动态规划4.1 一个百试百灵的判断标准无后效性加练贪心加得多了你一定会遇到这种题目看着像贪心写了个贪心交上去对了一半剩下那些错例怎么都想不通。这时候十有八九是你的解法其实需要动态规划而不是贪心。区分这两者的核心是无后效性。无后效性意思是一旦某个状态确定了它之后的决策不会受到之前是怎么到达这个状态的影响只跟当前状态本身有关。贪心之所以能用是因为它做了一个更强的假设每步的局部最优决策只由当前位置决定不会因为之前的具体路径不同而需要不同的选择。我自己的判断流程是这样的拿到题目先想能不能用排序单次扫描解决如果试了几个排序依据都觉得有反例就停下来想一下是不是需要记录一个状态集合比如到第i个物品时容量为j的最大价值。如果需要记录的状态数量是二维或以上那基本可以判断要用动态规划。举一个特别经典的例子0-1背包。如果按性价比价值/重量从高到低贪心大多数情况下能得出一个不错的解但不是最优解。因为背包问题有后效性——你先装了一个性价比高的轻物品可能导致后面一个重物品装不进去而这个重物品可能才是让总价值最大的关键。这就是典型的局部最优拼不出全局最优。4.2 一道看似贪心实则DP的加练题路径最大和为了让你更直观地感受到贪心和DP的边界我们看一个简单但陷阱十足的题给定一个n行n列的方格每个格子上有一个数字从左上角出发只能向右或向下走走到右下角求经过路径的最大数字和。很多人第一反应是贪心每次要么向右要么向下选数字较大的那个方向走。这个策略在部分数据上会得到正确结果但构造一个反例非常容易假设一个3x3的矩阵第一行第一个格子数字是1它右边是100、下边是1而右下角附近藏着一个更大的路径。每一步选较大的那个方向可能会一头撞进一个“局部富庶、全局贫瘠”的区域。正确解法是用动态规划。设dp[i][j]表示从左上角走到格子(i,j)的最大数字和转移方程是dp[i][j] val[i][j] max(dp[i-1][j], dp[i][j-1])。这样每个位置记录的是从起点到这里的全局最优而不是上一步看哪个顺眼。这道题的精髓在于它和贪心的差别只在要不要记录所有历史状态的最优值上特别适合用来检验自己有没有形成DP思维。我建议加练时做这样一件事拿这道题先用贪心写一遍再用DP写一遍然后构造几十组随机数据对比两个结果。做上一次你对这里不能贪的感受会非常深远比看十篇教程管用。4.3 处理这种选择题的实战策略先从贪心下手再用DP兜底在实际比赛中如果一道题不能确定该用贪心还是DP我的习惯是先用10分钟尝试贪心构造几个反例如果反例构造不出来而且时间复杂度允许就果断写一个DP的暴力版本或状态压缩版本去对拍用随机数据验证贪心的正确性。对拍是算法竞赛里验证贪心正确性的最实用手段——用一个简单的暴力程序哪怕是O(n^2)或O(2^n)当标准答案再让贪心程序跑同一组随机输入对拍几万次如果不一致马上就能发现你的贪心错在哪。这个方法对贪心加练特别重要。因为贪心的证明不是每次都能轻松写出来的而对拍能帮你快速排除错误直觉。我现在做贪心题的基本流程是先想排序规则和扫描方式然后构造两个极端反例再写个对拍程序跑几轮最后才交。5. 贪心加练题单与路线推荐按什么顺序刷才能把底层能力练扎实5.1 三个阶段的加练顺序入门巩固、思维强化、综合实战既然叫加练就得有强度、有顺序。我不建议你打开题库从第一题刷到最后一题那样效率太低。我把身边带过的同学和大佬们验证过的路线整理成三个阶段每个阶段解决一个能力缺口。第一个阶段是基础巩固期核心目标是练熟三类基础贪心排序贪心、区间贪心、最简单的堆维护。具体题单可以选区间调度类一题、区间选点类一题、区间覆盖类一题、任务收益题一题。这阶段不要追求难题而是要做到能讲清楚为什么这样排序。如果让你去解释区间调度为什么按结束时间排序你能画图说明白就算过关。第二个阶段是思维强化期核心目标是练熟反悔贪心和对拍验证。每天只做1到2道反悔贪心题但每道题都要求自己写一个暴力对拍程序拿随机数据验证。这个阶段会很明显地提升你对哪里能贪、哪里会翻车的敏感度。做完这个阶段的题你会发现自己再看陌生题的时候第一反应不再是瞎猜而是能直接构造出反例或者快速排除错误选项。第三个阶段是综合实战期把贪心和堆、并查集、差分约束这些工具混在一起。这个阶段的题不一定每道都叫贪心题但核心决策往往还是贪心。建议每道题做完后写30字的复盘笔记记录这题的排序依据是什么坑点在哪和之前哪道题类似。复盘是加练最容易被忽视但也最值钱的一步。5.2 写代码时的几个防坑清单排序条件、相等情况、边界溢出最后给一份我踩过无数次坑之后总结的防坑清单写贪心题的时候逐条对照排序条件写错是贪心题WA的最大来源。尤其是实现cmp函数时相等情况的返回一定要明确。C里比较函数必须满足严格弱序如果相等返回true会导致未定义行为Python里sort的key如果返回一个元组务必注意第二维是升序还是降序。边界情况不能漏。单元素数组、所有区间开始时间相同、所有截止时间相同、利润全部相同这些边界情况都要自己构造一遍测试数据覆盖到。处理时间或数量的地方注意爆int。区间调度里如果时间戳范围大可能要开long long任务收益题的利润累加也可能超int上限用long long更稳妥。堆的维护顺序要再三确认。反悔贪心用的堆是最小堆还是最大堆按截止时间排序是升序还是降序扫描到每个元素后是先判断合法性还是先做堆操作这些顺序差一行答案差之千里。我到现在做贪心题的时候还会因为cmp函数里一个等号的失误浪费一晚上。如果你也在这个问题上卡过不用自责——很正常加练的意义就是把这些坑一个一个踩平。反悔贪心是贪心算法里带一点灵性的变体它让你明白一个道理算法里没有绝对正确的选择只有随时准备接受更优解的机制。这种思维在真实工程里也很有用——线上策略出了问题不需要推翻重来而是用一套反馈机制淘汰掉不合适的部分保留更优的部分。这也是为什么我把反悔贪心单独拿出来讲这么一大章它不只是一道算法题更是一种解决问题的思维方式。如果你现在正被贪心题折磨我的建议就一句话不要只刷题每题都画图、写证明、跑对拍三件事做完你的加练才算真正有效。等你能在10分钟内判断一道题是贪心还是DP并顺手给出排序依据的时候这部分就算是彻底毕业了。