1. 贪心的直觉从哪来借会议室问题看清局部最优如何变成全局最优1.1 一个无代码版场景一天选满最多的会议昨天跟一个学弟聊到算法学习day28的贪心算法他第一反应是问贪心这个名字太直白了是不是就是每次选最优的那个跟抢菜一样我说对本质上就是抢菜但难点在于你怎么证明抢菜抢出来的结果确实是全场最好的。我举个例子。你一天有8个可用时间段公司给出了10个候选会议每个会议有固定的开始和结束时间有些时间还重叠。你想参加尽可能多的会议怎么排多数人的第一直觉是按开始时间最早去安排因为早起的鸟儿有虫吃。但实际做下来会发现一个开始特别早但拖得很长的会可能把后面三个短会全占了反而参加数量下降。正确的直觉应该是每一轮都选当前结束时间最早且不与已选会议冲突的那一个。这个策略在算法圈有个正式名字活动选择问题Activity Selection它是贪心算法入门阶段最经典的一道题。为什么先结束的就对因为结束得越早给后面留下的时间窗口就越宽。假如有两个会议都能选一个4点结束一个5点结束选4点的一定不亏——它最坏情况下也能覆盖5点那场能带来的全部可能性。这就是贪心的雏形你在每个岔路口都选眼下最有利的然后走到底不回头。1.2 为什么结束最早是答案而开始最早可能翻车为了讲清楚这件事先看一个稍微极端一点的例子。假如有3个会议A从9点到17点B从9点到10点C从10点到11点。按开始最早策略A和B、C的开始时间一样早但一旦选了A今天就只能开一场会选B再选C能开两场。而按结束最早策略第一轮先看所有会议里谁结束得最晚不对是最早。B在10点结束C在11点结束A在17点结束所以先选B。第二轮从10点开始扫描C可行A因为没结束所以不可行不对A还没开始所以可以再选C。最后还能开会吗A已经和C时间冲突了所以最终就是BC两场。为什么结束最早在这里一定对我换个方式来理解任何一场从9点开到10点的会都不可能比从9点开到11点的会更拖累后续安排。它等于用最短的时间占住同样的起始位置天然是性价比最高的。更严格地说这是替换论证——你先假设某个最优解里第一个选的会议不是结束最早的把它换掉换成结束最早的会议剩余的可选时间窗口只会变大不会变小那最优解就不会变差。一路替换下去你就把一个理想中的最优解一步步改造成了贪心解。1.3 贪心不是事后诸葛决策一旦做出就不再推翻很多人问贪心和走一步看一步试错有什么区别区别很大。试错允许你发现前面选错了再回头改贪心不允许它是一趟不归路。这一点在代码实现上特别明显。区间调度的算法写出来只有几行先把所有区间按右端点排序然后从左往右扫能选就选并更新当前已选区间的结束位置判断下一个区间是否和它有重叠。你看整个过程没有任何回溯或者递归分叉就是一条线走到底。也正因如此贪心算法的复杂度通常很低。排序O(n log n)扫描O(n)整体也就是O(n log n)。如果你在实现贪心的时候发现需要写多层循环去试探不同分支那你大概率不是在做贪心而是在写穷举。2. 动手之前先回答三个问题最优子结构、无后效性与可证明性2.1 问题一大问题的最优解里是否天然包含着子问题的最优解如果一道题能用贪心解那它背后通常藏着最优子结构整体最优意味着每一步切出来的子问题也是最优的。这个性质不是所有问题都具备。还是拿会议安排说。假设你从所有会议里选出了一个最优集合那么去掉第一场剩下的那些会议一定也是剩余时间段里的最优安排。如果剩余部分还存在一个更优的方案那替换回去整体方案就还能更优这跟原方案最优矛盾。这个逻辑成立贪心才有资格在子问题上递归地使用同一个策略。反过来看0-1背包问题容量为10三个物品分别重6、5、5价值分别为10、8、8。局部看第一个物品性价比不高但占空间大贪心选它剩下容量4放不下任何东西总价值只有10。可最优解是选两个5价值16。最优子结构在哪个环节断掉的呢当你选了第一个物品剩下的子问题是容量4物品只有第二、第三个这个子问题的最优解是0所以整体最优解变成10。可原始问题的真正最优解根本不该选第一个物品。这说明0-1背包里当前子问题的最优选择并不能拼出整体最优。2.2 问题二无后效性——已经做出的选择会不会影响未来的选择空间第二个判断标准是无后效性。口语地讲就是过去的选择只影响你现在站在哪不影响你接下来能做什么。会议室问题里无后效性是天然满足的你上一场会议开到11点结束下一场只要从12点开始就互不影响前面的选择不会产生副作用污染后面的候选集合。这就像坐公交车换乘你上一站在A站下车下一站你可以在B站、C站重新等车过去的线路不会限制你未来选哪条线的能力。但有些问题就不满足。比如带约束的作业调度每个作业有截止时间和收益一旦你选择了某个作业占用当前时间片后续所有作业的可用时间都会被压缩。这不是站在某个点重新开始的问题而是一个背包式的资源分配问题贪心经常在这里翻车。实战中判断无后效性有个土办法把决策过程演进到某一步时停下来问自己如果完全不知道过去是怎么走到这一步的只看当前状态是否还能做出等价正确的决策能才有贪心空间不能就考虑别的算法。2.3 问题三可证明性——你凭什么认为局部最优能推出全局最优我见过太多同学刷贪心题时靠感觉写代码样例过了就提交错一两次再换一种贪法继续试。这不是算法学习这是赌运气。严谨的做法是在写代码之前先试着证明一下贪心策略是正确的。哪怕是在脑子里做个草稿证明也能筛掉大量伪贪心。常见的证明手法是数学归纳法和替换论证。替换论证我前面已经演示过假设存在一个最优解先看贪心选中的那个元素把最优解里对应位置的元素替换成贪心元素证明答案不会变差然后对剩余部分继续用同样的逻辑。归纳法则是一步一步来证明第一步贪心选择正确然后假设前k步正确证明第k1步正确整个过程像多米诺骨牌。我自己的习惯是对于每道贪心题先写一句贪心策略是什么再写两到三行为什么它不会漏掉最优解。写不出来就先别急着码代码换一道题也行去查题解看清楚证明思路也行就是别硬写。3. 区间类问题的三板斧排序规则、扫描顺序、边界维护3.1 区间调度按右端点排序是最稳的贪心起手式进入了算法学习day28的刷题阶段你会发现贪心题目里有一大类是区间题它们的共同特征是输入一堆[start, end]区间要求你干某件事。区间调度是最典型的例子。我说一下标准解法把所有区间按end升序排序end相同则按start升序。扫描时维护一个last_end初始为负无穷。如果当前区间的start last_end说明不冲突可以选同时把last_end更新为当前区间的end。如果冲突跳过。为什么排序选end而不选start这个我在第1节已经用会议的例子讲过了不重复。核心记忆点就一句结束早的永远不亏。给你一个具体例子跑一遍区间[3,6]、[1,4]、[5,7]、[2,3]。按end排序后是[2,3]、[1,4]、[3,6]、[5,7]。扫描时选[2,3]last_end3[1,4]的start13跳过[3,6]的start33选上last_end6[5,7]的start56跳过。答案是2个区间。肉眼检查一下其实选[1,4]和[5,7]也是2个但贪心给出的[2,3][3,6]同样是最优数量。注意贪心不一定给你唯一的区间组合但它保证数量是最多的。3.2 最少点覆盖区间换个角度从选区间变成打点另一道经典问题是给你一堆区间问最少选多少个点可以让每个区间里至少包含一个点。这个问题和区间调度是镜像关系但贪心策略完全不同。区间调度是能选就选而打点问题是必选之时才动手。思路是这样的同样按end升序排序然后维护一个当前点的位置last_point初始为负无穷。扫描区间如果last_point已经落在当前区间里面start last_point end那这个区间已经被覆盖了不用管如果last_point在当前区间之前说明这个区间没有被覆盖那就必须打一个新点最省事的做法是打在当前区间的end上因为end越靠后越有可能覆盖后面的更多区间。注意这里的贪心直觉点打在越右边覆盖范围越大。所以当你必须打点时一定打在能打的范围内最右的位置也就是区间的右端点。这跟结束最早不亏是同一个逻辑右边端点越靠右对未来越有利。实现时仍然是排序后一次扫描时间复杂度O(n log n)。3.3 合并区间排序后一次遍历边界处理好就不会乱合并区间也属于这一挂给定一组区间把有重叠的合并起来返回合并后的不重叠区间列表。这个问题的正确贪心顺序是先按start排序再按end排序然后逐个判断当前区间能不能和已合并区间的最后一个合并。具体算法排序后把第一个区间放进答案列表。遍历剩余区间拿当前区间和答案列表里最后一个区间比较如果当前区间的start 人家已经合并出去的end说明有重叠那就合并新的end取二者的较大值如果没有重叠直接把当前区间作为新的一段加入答案。这里有个新手常犯的错误只判断了start小于等于末尾的end却忘了更新end时要取max。为什么因为可能出现新区间完全被旧区间包住的情况比如已有的区间是[1,10]当前区间是[2,3]如果不取max你的合并结果就会从[1,10]变成[1,3]白白丢掉一大段后面再来一个[5,8]就又得重新合并。合并区间的边界维护本质上是贪心扫描时的状态记忆这个状态记错了整个答案就崩了。4. 值类贪心的三种变式分配、跳跃与环形找油4.1 分发饼干排序后双指针满足谁都不如刚好够来得省区间题看的是时间轴上的取舍值类题看的是数字之间的匹配。分发饼干是贪心里非常入门的一道题很多算法学习day28的人第一道手写贪心就是它。题面简化一下你有一堆饼干每个饼干有个尺寸s[j]还有一堆小孩每个小孩有个胃口g[i]。一个小孩只能吃一块饼干只有当饼干尺寸 胃口时小孩才吃饱。问最多能喂饱几个小孩这种题最大的误区是大饼干喂大胃口小饼干喂小胃口这个模糊直觉。但如果你把两块饼干分别喂给两个胃口不同的孩子怎么分配效率最高答案是用小饼干去满足小胃口把大饼干留给大胃口。因为大饼干能做的事小饼干不一定能干反过来小饼干能满足的大饼干也能满足。从资源的角度讲尺寸小的饼干是稀缺的不能浪费在胃口大的孩子身上。实现起来就是两个数组都排序然后双指针用一个指针i指向当前孩子一个指针j指向当前饼干当饼干小于胃口j换下一块更大的满足胃口i、j答案加一。整个过程保证每块饼干在满足条件的情况下消耗得尽可能刚好不浪费。这题的难点不在代码而在你能说清楚为什么要排序、为什么要从最小的开始试。我见过不少人在原数组上直接贪心导致错误就是因为没有先排序。def findContentChildren(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 i4.2 跳跃游戏维护最远可达距离而不是只关心当前一步跳跃游戏的标准问法你在数组下标0处每个位置nums[i]表示从这最多能往后跳几步问能否跳到最后一个下标。这题一眼看上去像搜索或者动态规划但贪心可以做到一趟扫描。怎么贪维护一个变量farthest表示当前位置以及此前走过的所有位置能到达的最远下标。从左往右扫描每到一个新位置i先检查i是否大于farthest——如果大于说明这个位置根本走不到直接返回False。然后更新farthest max(farthest, i nums[i])只要某次更新后farthest n-1就可以提前返回True。这里的贪心点在于我不关心具体走了哪条路也不追求步数最少只关心可达范围不断的并集。每到一个位置当前能跳到多远就更新一次最远边界像滚雪球一样把可达区间越推越远。很多人会想当然地每一步跳最远这反而可能跳过头。因为farthest是历史所有位置的综合结果不是当前位置的跳跃结果。比如nums[2, 5, 1, 0, 0]从0位跳到2位远不如从1位跳到5位远。如果你在某一步贪最近就错了正确的贪法是把所有可达位置的跳跃能力并起来取一个全局最大值。这道题的思考顺序建议是先写出最朴素的模拟每一步跳最远然后手动跑几个反例发现不对再改成维护farthest的写法。亲测这个发现问题、修正模型的过程比直接背答案有用得多。def canJump(nums): farthest 0 n len(nums) for i in range(n): if i farthest: return False farthest max(farthest, i nums[i]) if farthest n - 1: return True return False4.3 加油站全局油量判据是这题最容易被忽略的证明加油站问题是跳跃游戏的亲戚圆环上有若干加油站每个站可以加油gas[i]每开到下一站要消耗cost[i]车从某个站出发油箱为空问能不能绕一圈如果能返回出发站的编号。我的第一反应是枚举起点每个起点模拟一圈复杂度O(n²)数据一大就跪了。贪心解法可以做到一趟扫描。它的核心判据是如果总的gas之和小于总的cost之和那么无论如何都跑不完一圈直接返回-1。既然总量够就说明存在至少一个可行起点。接下来找起点。用一个变量total记录全程净油量用current记录当前起点下的剩余油量。从左到右扫描持续累加gas[i] - cost[i]如果current在某个位置变成负数说明从当前起点出发是失败路线那么从这段失败路线的任何一个中间站出发也不可能成功。为什么因为如果某个中间站能成功那它至少该在这个站到失败点之间保持当前余额非负而事实上失败点之前的累计已经小于0了根本翻不过去。这是一个非常重要的反证逻辑。一旦current 0就把起点重置为i 1同时current清零。扫描结束后如果total 0start就是答案。def completeCircuit(gas, cost): total 0 current 0 start 0 for i in range(len(gas)): total gas[i] - cost[i] current gas[i] - cost[i] if current 0: start i 1 current 0 return start if total 0 else -1这道题我当年折腾了挺久最后总结出一个非常实用的心法遇到环形问题先算总账总账可行再在局部用失败区间重置起点的方法找入口。总账判据保证了答案存在性局部重置保证了不重复计算。5. 反例是最好的老师贪心与动态规划的分界线5.1 经典反例0-1背包为什么不能按性价比贪心前面我提前用0-1背包做了例子这里再展开一点因为它太能说明问题了。分数背包物品可以切碎可以贪心直接按单位重量价值排序能装多少装多少0-1背包不能因为每个物品只有拿或不拿两种状态物品不可分割。从数学上看分数背包的决策空间是连续的每步都可以做一个微调的局部最优0-1背包的决策空间是离散的组合爆炸局部最优和全局最优之间隔着一条巨大的鸿沟。我见过一个很简明的反例背包容量10物品A重量6价值9物品B重量5价值5物品C重量5价值5。按性价比贪心A排第一选它之后只能剩4容量价值9但正确答案是B加C价值10。每次遇到这种反例我都建议自己动手在纸上画一下。画完之后你自然就会理解为什么0-1背包最后要写成dp[i][j]而不是一个排序加贪心。动态规划之所以敢在指数级选择空间上找出最优解靠的是把子问题存下来用重叠子问题的复用对抗组合爆炸。贪心则完全不回头看一条路走到黑。无后效性成立时回头看是浪费不成立时回头看你又回不来那就是陷阱。5.2 钱币找零硬币面值不同贪心结论完全反转找零问题太适合做这类对比了。在人民币、美元这种标准货币体系下用贪心找零是对的尽量用大额面值剩下的用小额补齐硬币和纸币数量一定最少。可你一旦自定义硬币面值比如硬币面值是1、3、4目标金额是6贪心就会出错。贪心先拿一个4再拿两个1共3枚但正确答案是332枚。这个反例的价值不在于题目本身冷门而在于它提醒你贪心策略的正确性依赖于数据结构、面值结构或者某种特殊性质而不是普适真理。很多人刷了一段时间贪心后容易膨胀见题就贪感觉好像可以然后开始写代码。遇到这种心态找零问题是最好的清醒剂。实际面试里面试官可能会给你一个非常规的硬币组合专门看你会不会踩这个坑。你要是能在笔试阶段就主动验证这个面值体系是否有整除关系或者更严格的贪心性质就会显得扎实很多。5.3 无后效性失效的瞬间为什么动态规划要记录所有状态动态规划和贪心看起来都在做选最优最本质的区别是动态规划会把每一步的所有可能状态都算出来然后慢慢合并贪心只保留一条当前最优路径。用一个类比。你要从城市A开车到城市D中途经过B和C。贪心是每到一座城市就根据当前油量和距离选一个自认为最好走的下一段路选了就锁死动态规划则是每到一座城市把从起点到这个城市的最小成本先记下来同时把从这座城市出发的所有可能路线都估个价最后统一汇总。在无后效性成立的情况下这两个结果往往一样不成立时动态规划仍然能通过状态枚举兜底贪心就彻底失控了。所以我的判断标准很简单如果题目要求输出最优解的具体方案、或要求方案在所有约束下严格最优我会先试着用动态规划模型去分析一下状态怎么定义只有当我能证明当前选择不影响未来状态空间时我才放心用贪心。这不是保守是从频繁翻车中总结出来的纪律。6. 实操经验从读题到证明的四步法与三个常见卡点6.1 四步法把一道贪心题从感觉会练到证明过我自己的刷题流程总结下来是四步。第一步读题后先写出贪心策略的一句话描述不许模棱两可必须具体到面对什么信息、怎么排序、选什么、更新什么这种颗粒度。第二步想反例。我会先假设这个贪心策略是错的然后刻意构造一个可能让它翻车的小数据集。如果几分钟内构造不出反例我才会进入证明环节如果一构造就翻车说明策略不对赶紧调整。这一步没啥技巧就是要勤快要敢怀疑自己。第三步做证明。最简单的公式化证明就是替换论证具体到代码里就是回答两个问题第一个被贪心选中的元素在某个最优解里是什么角色能不能替换替换后剩余子问题是不是与原问题同构。这两个问题答顺了策略基本就稳了。第四步边界测试。空数组、只有一个元素、全部相等、全部相邻重叠、答案为零等情况一个不能少。特别是在算法学习day28这种连续刷题节奏里前三步消耗了大量脑力第四步最容易偷懒但漏边界恰恰是面试时最扎心的事故。6.2 我在刷题中踩过的三个坑第一个坑是把排序后贪心和贪心混为一谈。很多题确实需要先排序但排序只是预处理不是贪心本身。真正决定对错的是排序之后怎么扫描、怎么更新状态。我开始学的时候经常写完一个排序就觉得大功告成结果在扫描阶段少了一个状态更新代码跑出来错得一塌糊涂。第二个坑是忽略了正确性的局部性。我做合并区间时默认两个区间重叠但新区间完全被包含的情况不需要特殊处理结果把[1,10]和[2,3]合并成了[1,3]后面所有判断全部连锁出错。这个教训告诉我贪心扫描时维护的状态变量要当成一个独立的小问题来处理不能想当然。第三个坑是排序键写错。区间调度按end排区间合并按start排这两个顺序容易记混。我后来养成了一个习惯每次写区间题都先问自己排序的依据到底是什么然后在代码注释里写清楚理由。别看这习惯土它能防止你在状态紧张时犯最基础的错误。6.3 给新手的学习顺序和练习清单如果让我给一个循序渐进的学习路径我会建议按这样的顺序练第一梯队入门找感觉分发饼干、柠檬水找零、摆动序列、跳跃游戏。这几题代码量都很小目标是把贪心策略证明的思维模式建立起来。第二梯队区间类全家桶区间调度、最少点覆盖、合并区间、插入区间。这组的价值是让你彻底吃透排序规则扫描维护这一套组合拳。第三梯队进阶综合加油站、分发糖果、根据身高重建队列、活动安排。这些题有的需要从全局想通约束有的需要处理排序后的人为规则综合性更强。梯队之间不要跳至少把每一道的证明思路在纸上写一遍。贪心的特点就是代码都好写证明都难想。代码能力被高估了真正拉开差距的是你能不能在三分钟内说清楚为什么这么做是对的。这恰恰是短期冲刺刷题最练不出来的部分得靠日积月累的刻意练习去沉淀。最后再分享一个我自己的习惯每次刷完一道贪心题我会在题目旁边补一句话——这道题贪心的理由是______如果不贪心会错在哪。时间长了你会发现所有正确贪心的理由长得越来越像所有翻车的反例也长得越来越像。到那个时候贪心算法在你的工具箱里就不再是一门玄学而是一把真正趁手的工具。