1. 做贪心题之前先把底层逻辑拆明白很多人刷题遇到“贪心”两个字第一反应是“这不就是凭感觉选一个最优解吗”。说实话我刚接触贪心算法的时候也是这个心态结果一道题能错三遍而且每次错的理由都不一样。后来我把贪心题刷了一轮才慢慢摸清它背后的规律。贪心算法Greedy Algorithm的核心是在每一轮决策时只盯着眼前的最优选择不去考虑后面会怎么样。它跟动态规划最大的区别就在这动态规划会把所有子问题的答案都算一遍贪心则不回头、不回溯选了就是选了。这个思路听起来简单真正难的是判断“这道题到底能不能贪心”。**能用贪心解的题通常要满足两个条件一是局部最优能推导出全局最优二是后面的决策不会影响前面已经做完的选择。**如果一个题目的选择会互相牵制贪心基本就会翻车。举个例子你感受一下。周末爬山你要从山脚爬到山顶中间有无数条岔路。如果每条岔路都竖着牌子告诉你“走这条路接下来能到达的最高点是哪里”那你每到一个岔路口选最高点最大的那条路最后一定能到山顶因为所有路最终都通向山顶。但现实爬山不是这样的你选了左边这条路后面可能根本没有路通往更高的地方这就是局部分数高但全局失败的情况。贪心算法能解决的问题就是这种“只要你每一步都选当前看起来最有利的最后结果就是全局最有利”的问题。所以我在刷贪心题之前会先自己问三个问题这个题能不能拆成若干个独立的子步骤每个子步骤的局部最优是不是真的能叠加成全局最优如果放弃局部最优全局是否可能更好如果可能那这题大概率不能贪心。这三步过滤下来基本能筛掉一半的“伪贪心”题。剩下能安心用贪心的题目解题代码通常都很短难的是证明和思考过程。这也是为什么面试里考官特别喜欢考贪心代码量不大但能考出你真的懂不懂。接下来我就用几道很有代表性的题目把贪心最常见的几类解题套路拆开讲一遍。题目难度从入门到进阶都有代码我统一用 Python 写思路也适用于 C 和 Java。2. 入门题目拆解从最直观的两道题开始找手感2.1 分发饼干排序加匹配最简单的贪心模型题目是这样的有一群孩子每人有一个饥饿度有一堆饼干每块饼干有一个尺寸。只有当饼干的尺寸大于等于孩子的饥饿度时孩子才能吃饱。问最多能让几个孩子吃饱。这道题的贪心策略非常直白**给每一个孩子分饼干时选择刚好能满足他、又不过度浪费的那块。**翻译成操作就是先把孩子的饥饿度和饼干尺寸都排序然后用两个指针从头开始扫遇到能满足的饼干就分出去满足不了就换下一块更大的饼干。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 i这个代码只有几行但里面的坑在于“为什么要排序”。如果不排序你拿到的饼干可能完全乱序你没法判断当前孩子吃这块行不行、后面有没有更好的。排序之后问题变成了有序数组的匹配问题贪心就有了依据最小的饼干先试最小的孩子不行就扔到下一块。我最初做这题的时候犯过一个错误想着从大饼干开始分配给最大的孩子分最大的饼干。结果代码写出来也没错但理解上绕了很多弯。后来才发现这题有两个等价的方向要么“小饼干喂小孩子”要么“大饼干喂大孩子”本质上都是尽量不让饼干尺寸浪费。贪心题里这种“从哪个方向贪心都一样”的题目不少关键是选一个实现起来最顺的方向。2.2 柠檬水找零贪心策略藏在“优先用大钞”里这道题是 LeetCode 上有名的简单贪心题你卖柠檬水一杯 5 美元顾客会排队付款可能会付 5、10、20你需要给每个人正确找零初始手上一分钱都没有判断能否给所有顾客成功找零。题目看着像模拟题但真正考的是找零时的面额选择策略。顾客给你 20 的时候你要找 15手上有 10 和 5 的话应该怎么找普通人的直觉是“先把大额钞票用出去”这正好就是贪心策略能用 10 块的就不用两张 5 块的。def lemonadeChange(bills): five ten 0 for bill in bills: if bill 5: five 1 elif bill 10: if five 0: return False five - 1 ten 1 else: if ten 0 and five 0: ten - 1 five - 1 elif five 3: five - 3 else: return False return True这里为什么要优先用 10 而不是 5因为 5 美元是最灵活的货币它可以应对所有找零场景而 10 美元只能用于给你付 20 的顾客找零。形象的比喻是5 块是万能钥匙10 块是特殊钥匙。特殊钥匙能在特殊场合用但万能钥匙所有场合都能用所以你手里的特殊钥匙应该优先消耗掉把万能钥匙留在后手。这道题的答案代码虽短但它是“贪心策略选择”的极好示范。很多贪心题的难点不在数据结构而在你能不能想清楚“每一步什么才是最优选择”。柠檬水找零里最优选择的标准就是保留灵活性最大的资源。3. 扫描一遍的贪心把大问题拆成每天的局部判断3.1 买卖股票的最佳时机 II把利润拆进每一个上升区间买卖股票系列的题目特别适合讲贪心因为生活经验人人都懂。这个版本的要求是你可以在每一天决定买或卖但手里最多持有一股而且当天卖出后当天还能再买入问怎样能获得最大总利润。很多人看到这题第一反应是动态规划因为它跟“最佳时机 I”只能买卖一次长得很像。但这题有个关键条件是“可以多次交易”这反而让贪心有了用武之地只要明天的价格比今天高那今天买入、明天卖出就一定赚这个局部利润可以累加。def maxProfit(prices): profit 0 for i in range(1, len(prices)): if prices[i] prices[i-1]: profit prices[i] - prices[i-1] return profit代码就这么短。关键在于理解为什么可以只看相邻两天你不需要预测未来只要明比今高就赚一笔。这跟你现实中买菜一样今天 3 块明天 4 块你今天买明天卖赚 1 块后天 5 块就再赚一块。所有连续上涨的日子你每天都参与就把整段涨幅全部吃到了。有人会纠结一个问题如果我今天买明天卖明天又买后天卖跟今天买后天卖赚的是一样多吗假设三天价格是 3、4、5第一种操作赚 112第二种操作买在 3 卖在 5 赚 2结果完全一样。既然结果一样贪心策略反而更简单因为它不需要判断“哪里是顶点”只需要无脑捕捉每一个上升区间。3.2 跳跃游戏维护“最远可达范围”是关键跳跃游戏是另一道非常经典的贪心题。给你一个非负整数数组每个数字代表你在当前位置最多能往后跳多远初始站在下标 0问你能不能跳到最后一个位置。这题暴力搜索会超时动态规划能做但有点绕贪心却异常简洁**你不需要关心具体跳到哪里只需要维护一个“当前能到达的最远下标”。**遍历数组时只要当前位置在下标范围内就更新最远可达距离一旦最远可达距离超过终点就说明能到。def canJump(nums): max_reach 0 for i in range(len(nums)): if i max_reach: return False max_reach max(max_reach, i nums[i]) return True为什么这里贪心成立因为每到达一个位置你能跳到的最远距离是固定的至于跳到哪里对后续的影响全部体现在最远距离这一个数值上。换句话说“跳得远的方案”永远不会比“跳得近的方案”差因为你完全可以少跳几步停在中间某个位置但多跳出来的可能性是你额外获得的。这种“能走多远就走多远”的优势独占性正是贪心能生效的原因。我第一次做这题的时候总想着模拟跳跃路径比如当前在 3下一步是跳到 1 还是 7要不要留点后路。后来发现完全不用纠结最远可达距离已经包含了所有可能路径的信息只要维护一个最大值就够了。这个思维转变很重要它让我意识到很多贪心题表面看是路径选择问题本质上是区间覆盖问题。3.3 跳跃游戏 II从“能不能到”进阶为“最少几步”跳跃游戏的进阶版是保证你能跳到终点让你求出最少跳几次。这题同样用贪心但思路比上一题多一层思考。核心策略是**在每一跳的范围内选择能让你跳得最远的下一跳。**翻译成代码就是维护当前这一跳能到达的边界以及边界内所有位置能扩展出的最远距离。def jump(nums): n len(nums) if n 1: return 0 steps 0 cur_end 0 far 0 for i in range(n - 1): far max(far, i nums[i]) if i cur_end: steps 1 cur_end far if cur_end n - 1: break return steps这个代码里的cur_end是当前这一跳的边界一旦遍历到边界说明必须再跳一次这时候把边界更新为之前累积的far。整个过程像是一层一层地向外扩张每一层就是一步。这题的难点在于理解“为什么到边界才增加步数”。你站在位置 0能跳到 3那么在 1、2、3 这三个位置里你实际上在“免费”地探索它们能跳多远。当你走到位置 3 的时候说明第一跳能覆盖的范围已经遍历完了这时你才需要决定第二跳从哪里开始。贪心的体现就是第二跳一定从“第一跳覆盖范围内能到达最远”的那个位置开始。3.4 扫描类贪心的共同心法当前最优加范围扩张把买卖股票、跳跃游戏、跳跃游戏 II 放一起看你会发现它们有个共同模式从左到右扫描一次维护一个不断更新的“最优状态”。买卖股票里维护的是“累计利润”跳跃游戏里维护的是“最远可达下标”跳跃游戏 II 里维护的是“本步边界”和“全局最远”。这种题型的特征是问题被天然地按顺序拆成了多个决策点每个决策点的最优解只依赖之前的信息不依赖未来。用大白话说就是“走到哪算哪但每一步都要把当前积累的优势用到极致”。遇到这类题我建议你养成的第一反应是能不能从左到右扫一遍扫的过程中用一个变量记录当前最优到终点直接出答案。如果这个思路能走通代码量通常不会超过二十行而且不容易出 bug。如果不行再考虑动态规划或者其他方法。4. 区间问题排序之后贪心面试最爱考的高频套路4.1 无重叠区间移除最少区间让剩下的区间互不重叠区间问题是贪心算法里的重头戏因为它有非常固定的解题套路。这题的要求是给定一组区间问最少需要移除多少个区间能让剩下的区间互不重叠。我第一次看到这题脑子里第一反应是“移除哪些区间要看它们重叠得多严重”于是想着按区间长度或者重叠次数排序。但正确答案的思考角度正好相反不是选移除哪些而是选保留哪些。尽量保留更多的区间移除的就是总数减去保留数。def eraseOverlapIntervals(intervals): if not intervals: return 0 intervals.sort(keylambda x: x[1]) end intervals[0][1] count 1 for i in range(1, len(intervals)): if intervals[i][0] end: count 1 end intervals[i][1] return len(intervals) - count这里的贪心选择是**每次都选结束时间最早的区间保留。**结束时间早意味着它给后面的区间留下的空间更大所以你保留它的“机会成本”最小。这种“选最早结束”的策略在英文里叫 Earliest Finish Time是区间调度问题的经典解法。为什么按左端点排序就不行我试过按左端点从小到大排然后尽量选左端点大的结果发现遇到一个区间特别长的时候排序结果会误导你比如[1, 100]会排在[2, 3]前面但你显然应该保留[2, 3]。按结束时间排序后[2, 3]排在前面贪心策略自然就会选中它。这个排序方向的差异几乎是区间题最大的坑。4.2 用最少数量的箭引爆气球区间交集和区间重叠的区别无重叠区间是“去掉重叠的”而这道题是“把重叠的合并在一起”。题目描述有点长墙上有一些气球每个气球占据一个水平直径区间你可以从任意 x 位置垂直射出一支箭只要箭经过的位置包含某个气球的区间这个气球就会爆问你最少需要几支箭。其实翻译成人话就是**把重叠的区间归为一组问最少分几组每一组里的区间都有交集。**和无重叠区间那题不同这里不需要移除任何区间只需要统计要分几组。def findMinArrowShots(points): if not points: return 0 points.sort(keylambda x: x[1]) arrows 1 end points[0][1] for i in range(1, len(points)): if points[i][0] end: arrows 1 end points[i][1] return arrows仔细看这段代码跟无重叠区间的代码几乎一模一样唯一区别是判断条件里一个是一个是。无重叠区间里两个区间端点相接不算重叠、可以共同保留但气球题里如果箭正好在端点处穿过两个气球一起爆所以端点相触也算同组。这个细微差别正是两题的分水岭。这种“换一个符号就换了一道题”的情况在算法题里特别常见。所以我不建议死记代码而是建议理解每一题的语义边界重叠的定义到底是什么包含不包含端点不同定义直接决定了还是。理解到这一层你就不是背代码的人而是真的掌握了区间问题的精髓。4.3 区间类贪心的易错点排序规则、边界判定、空区间处理区间题做多了我发现错误基本集中在三个地方。第一个是排序规则。无重叠区间按右端点排合并区间按左端点排都是先排序再用贪心但排哪个端点取决于你要干什么。如果你要“尽量留更多的区间”按结束时间排如果你要“把区间合并覆盖”按开始时间排。这个规则一旦错了后面全完蛋。第二个是边界判定。区间题里最大的是[1,2]和[2,3]算不算重叠这一个判断就够让你调试半天。我习惯的做法是在动笔前先定义清楚重叠是start end还是start end其实区间题还有左闭右开、左闭右闭等写法不同的语言和题目描述可能不同建议统一用题目最原始的定义来思考。第三个是空输入和单个元素。intervals为空时直接返回 0这个还好很多人不会漏但只有一个区间时要返回 0 个移除箭头、1 支箭这种边界情况代码一开始就要处理对不然后面数据一多就容易出现索引越界。5. 贪心翻车现场与经验总结什么时候局部最优不等于全局最优5.1 经典反例一0-1 背包问题贪心算法最大的敌人是“当前的选择会影响后面的选项”的情况。最有名的反例就是 0-1 背包问题。假设背包容量为 10有三件物品A 重量 6 价值 12B 重量 5 价值 10C 重量 5 价值 10。按单位价值贪心A 是 2B 是 2C 也是 2你会先选 A结果剩下容量 4 什么都装不了总价值 12。但最优解是选 BC总价值 20。贪心在这里彻底失灵因为你选了 A 之后剩余容量不足以再装任何东西而这个后果在选 A 时是看不出来的。对比之下分数背包物品可以切割为什么能用贪心因为切割后没有“选了这个就不能选那个”的限制当前拿最值钱的单位永远不会对未来造成伤害。这个对比很好地说明了贪心的适用边界有互斥约束的决策不能盲目贪心。5.2 经典反例二硬币找零问题再看一个生活化的例子硬币找零。假如有 1、3、4 三种面值的硬币需要凑出 6 块钱。贪心策略会先用最大的 4 块剩下 2 块用 1 块凑得到 411一共 3 枚硬币。但最优解其实是 33只要 2 枚。很多教科书里说“硬币找零可以用贪心”其实不够严谨。只有在硬币面值满足特定条件比如人民币的 1、5、10、20、50时贪心才成立换成任意的币值组合就会翻车。所以你在面试里碰到这类题千万要先确认能不能贪心不能想当然。5.3 怎么证明贪心策略是对的看到这里你可能会有个疑问那做题的时候怎么知道这题能不能贪心总不能每道题都靠试错吧答案是**用下笔前几分钟做逻辑推导。**常见的证明方法有两种。第一种叫交换论证。假设存在一个最优解它某一步的选择跟贪心策略不一样你证明把这个不一样的选择换成贪心选择后结果不会变差。这样一步步换过去就能说明贪心解也是最优解。第二种叫反证法。先假设贪心解不是最优解那必定存在一个更优解。然后分析一下更优解的第一个决策如果它跟贪心不同你证明它可以通过调整变成贪心选择且不更差从而推出矛盾。跳跃游戏这类“覆盖范围”题就很适合反证法如果存在一个方案跳得比最远覆盖策略更远但你每一步都取了最大值最大值不可能被超越矛盾自然就出来了。不是每道题都值得写严格证明但至少要在脑内过一遍“这个局部最优真的不会坑到我吗”。我自己的习惯是在学习阶段每道贪心题都写一遍思考过程哪怕写得很简陋也强迫自己想清楚而不是看一眼题解然后说“哦原来是贪心啊”。5.4 刷题与面试中的实战建议最后聊点实用的经验。第一贪心题在面试里出现频率极高因为它代码短、考察思维。如果面试官给你一道题你判断它是贪心可以快速写下十几行代码这比写动态规划节省大量时间也给面试讨论留出空间。但如果判断错了贪心代码跑不出正确结果会非常尴尬。第二我建议刷题时把贪心相关的题目集中在一段时间内刷完比如一周只刷贪心题。因为贪心题的“手感”很重要连续刷能帮你建立条件反射看到“最多”“最少”“最大”这类关键词就能快速想到排序、扫描、区间维护这几板斧。第三遇到不会做的贪心题不要急着看题解先自己想几个能举的反例。比如你觉得这题应该按某个量排序就尝试构造一组数据让这个排序看起来不对劲。构造反例的过程其实就是在检验你对贪心选择的理解。第四我踩过最多次的坑是“排序方向错了”。很多题都需要排序但按左端点排还是右端点排升序还是降序差之毫厘谬以千里。我后来总结了一个办法先确认你的贪心策略是什么再确认排序如何支撑这个策略。比如无重叠区间要选最早结束的那就必须按右端点升序排排序是为了让“最早结束”这个选择可以从左到右顺理成章地做出来。这几道题刷下来你会发现贪心算法其实没有传说中那么玄乎。它不是什么高深的理论更像是一种思维习惯在每一步都问自己怎么做能让当前局部最优并且相信这些局部最优能凑成全局最优。想清楚这句话你就已经掌握贪心的精髓了。剩下的就是多刷几道题把这种思维练成肌肉记忆。