前阵子一个准备算法面试的朋友跟我抱怨“贪心算法刷了二十道题还是觉得玄学。对着题解看每个局部最优的选择都很有道理自己上手写样例一多就翻车。”这个感受我太熟悉了。力扣hot100里贪心相关的题其实不多撑死了六七道但每道都极其典型覆盖了面试里最高频的几个模型股票买卖、跳跃游戏、区间贪婪、环形数组判定。把这些题吃透比无脑刷五十道零散的贪心题有用得多。这篇博客我打算把hot100里贪心相关的题目全部过一遍按模型分类拆解每个模型讲清楚三件事贪心策略是什么、为什么是对的、边界条件容易错在哪。适合两类人看一类是准备大厂算法面试、时间紧任务重的同学另一类是刚开始刷力扣、对贪心只有一个模糊概念的新手。1. 先看全局贪心在hot100里到底占多少、考什么1.1 hot100里的贪心题数量不多但模型非常集中以目前常见版本的力扣Hot 100题目清单来看能被明确归入“贪心算法”标签的题大致是这几道题目题号难度核心模型买卖股票的最佳时机121简单前缀最小值 / 一次交易买卖股票的最佳时机 II122中等差分段累加 / 无限次交易跳跃游戏55中等维护最远可达边界跳跃游戏 II45中等最少步数 / 分层跳跃划分字母区间763中等区间边界合并思想加油站134中等环形数组 / 总量判据另外像“根据身高重建队列406”这类题虽然很多题单把它归进贪心标签但它本质上考的是“排序后按规则插入”贪心成分很弱更像是自定义排序插队的综合题。我在刷题时更倾向于把它归为排序专题这里也就不展开说了。还有一个特殊的坑有人会在讨论区问“腐烂的橘子是什么题型”。这题用的是多源BFS广度优先搜索不是贪心。它虽然问的是“最少分钟数”但扩散过程天然适合按层模拟按贪心去解反而容易漏掉多源同时扩散的情况。这部分我在第4章详细讲先把结论放在这里——贪心在hot100里的出题范围非常窄窄到完全可以集中突破。1.2 贪心的底层逻辑什么时候局部最优能推出全局最优很多人对贪心恐惧是因为它不像动态规划那样有固定的状态转移方程。动态规划是把所有可能的状态都算一遍贪心则是每步只做一个选择不做回头路。要想用贪心题目必须满足一个隐藏前提每一步的局部最优选择恰好也是全局最优解的一部分。这个前提在数学上叫“最优子结构”和“贪心选择性质”。举个生活中的例子你就明白了。假设你下午要开会会议室里有若干个时间段可预订每个时间段都有开始时间和结束时间你想安排尽可能多的会议。最直观的策略是什么每次选“结束时间最早”的那个会议。为什么因为结束得越早给后面留下的可用时间就越长这个选择不会让整体安排变差。这就是一个教科书级的贪心模型local choice决定了全局结果。反例也很容易举自助餐拿菜。如果每次都选当前看起来最好吃的那一口最后可能吃撑了还没吃到真正想吃的因为胃容量有限。这说明“当前最优”并不总是能推出“全局最优”。刷贪心题的过程说白了就是在训练你识别“哪些问题满足那个前提哪些不满足”。hot100里的这几道题全都是满足前提的经典模型所以非常适合用来建立直觉。2. 六道经典题拆解每一道都代表一类模型2.1 股票买卖系列121和122的差别就是“一次”和“无数次”这两个题放一起对比刷效果最好。121题只允许一次交易也就是你只能挑一天买入、之后挑一天卖出求最大利润。最经典的贪心解法是一遍遍历记录遍历到今天为止出现过的最低价格然后计算“如果今天卖出能赚多少”不断更新最大值。class Solution: def maxProfit(self, prices: List[int]) - int: if not prices: return 0 min_price prices[0] max_profit 0 for price in prices[1:]: min_price min(min_price, price) max_profit max(max_profit, price - min_price) return max_profit为什么这个局部记录是有效的因为对于任意一天的卖出动作想获得最大利润买入日一定是之前价格最低的那一天这是无可争议的最优前置条件。我们不需要知道具体哪一天买入只需要维护“截至目前的最低价”这个状态就够了。复杂度O(n)时间、O(1)空间是这个题最优解。122题则是无限次交易你可以今天买明天卖也可以持有多天再卖唯一限制是手里同时只能有一支股票。这个题的贪心策略一句话就能说清只要今天的价格比昨天高就认为这一段差价可以赚到。class Solution: def maxProfit(self, prices: List[int]) - int: profit 0 for i in range(1, len(prices)): if prices[i] prices[i - 1]: profit prices[i] - prices[i - 1] return profit这里有个很多人想不通的点股票交易不是应该“低买高卖”吗为什么每天比较相邻差价也算你拿个三段价格 [1, 3, 5] 试一下就明白了。一次交易买1卖5赚4分两次交易买1卖3、买3卖5总共赚(3-1)(5-3)4。结果一样。也就是说任意一段单次交易的大利润可以被拆成一串相邻差价的和。既然题目允许无限次交易把所有正差分累加就是上界而累加所有正差分显然可达所以这就是最优解。注意121题的解法本质上也可以理解为“DP的滚动优化”但大部分人接受它作为贪心入门题更自然。后面会细说贪心和DP的边界问题。2.2 跳跃游戏系列维护“最远可达边界”就够了55题跳跃游戏问的是从下标0出发每个位置上的数字代表你最多能往后跳多少步能不能跳到最后一个位置。这个题的贪心策略叫“维护可达最远距离”。class Solution: def canJump(self, nums: List[int]) - bool: n len(nums) farthest 0 for i in range(n): if i farthest: return False farthest max(farthest, i nums[i]) if farthest n - 1: return True return True核心思路极简单遍历每个位置如果当前位置已经在可达范围内i farthest就尝试更新最远可达边界一旦发现某个位置根本够不到i farthest说明中间出现了断点直接返回False。为什么贪心成立因为“能到达的最远位置”是一个单调不减的上界我们不需要具体走哪条路径只要这个上界能覆盖终点就必然存在一条合法路径。这题不做路径规划只做可行性判定所以贪心是自然的。45题跳跃游戏 II升级了要求返回到达终点的最小跳跃次数。这题贪心解法有点像“按层推进”的BFS把当前位置能跳到的最远位置看成一层的右边界走到边界时计一次跳跃然后更新边界为下一层能到达的最远位置。class Solution: def jump(self, nums: List[int]) - int: n len(nums) if n 1: return 0 steps 0 cur_end 0 # 当前这一跳能到达的右边界 farthest 0 # 下一跳能达到的最远位置 for i in range(n - 1): farthest max(farthest, i nums[i]) if i cur_end: steps 1 cur_end farthest if cur_end n - 1: break return steps这里最容易翻车的是循环边界。我在写第一版时习惯遍历整个数组结果在最后一个位置时又触发了一次跳跃计数多算一步。后来发现循环只需要走到 n - 2 就可以或者像上面代码里一样遍历到 n - 1 但通过 break 退出。只要记住到达最后一个位置后就不需要再跳了这类边界问题就能避免。45题为什么能贪心而不是必须DP因为每一步选择“能跳得最远”的那些位置集合不会因为之前的跳跃方式而变小跳到最远意味着给后续留下的选择空间最大所以跳数一定不会比保守策略多。2.3 划分字母区间先记录每个字符的最后出现位置763题“划分字母区间”是hot100里比较有意思的一道题给你一个字符串要把字符串划分成尽可能多的片段要求同一字母最多只出现在一个片段中返回每个片段的长度。我第一次见这道题时完全没思路后来理解了核心思想就发现它特别简单先扫一遍字符串记录每个字符最后一次出现的下标。然后再扫一遍维护当前片段的一个右边界end每遇到一个字符就把end更新为max(end, 该字符最后一次出现的下标)。当遍历的位置i等于end时当前位置就是片段边界切一刀。class Solution: def partitionLabels(self, s: str) - List[int]: last {} for i, ch in enumerate(s): last[ch] i res [] start end 0 for i, ch in enumerate(s): end max(end, last[ch]) if i end: res.append(end - start 1) start end 1 return res这个策略为什么是贪心因为每个字符的最后一次出现位置是一个不能突破的硬约束。当前片段里只要包含某个字符片段的右边界就必须至少延伸到该字符的最后出现位置。在每步中我们都把右边界推到这个约束的最大值因此不会漏掉任何必须包含的字符也不会产生不必要的更长片段。当i走到end时说明当前片段已经“被迫完整”了此时切割就是题目允许的最早切割点能保证片段数量最多。这个模型和45题的farthest变量本质上是一回事维护一个不断向右推进的目标边界等到遍历指针撞上边界时做一次操作。模型识别出来之后两道题就是同一套思路。2.4 加油站环形数组上的贪心结论134题“加油站”长这样在一个环形路线上有若干加油站第i个加油站有gas[i]升油从第i站开到第i1站需要消耗cost[i]升油。你的车一开始油箱是空的问从哪个站出发能走完全程如果不存在则返回-1。这题贪心解法的代码非常短但背后的推理值得好好讲一遍。class Solution: def canCompleteCircuit(self, gas: List[int], cost: List[int]) - int: total 0 cur 0 start 0 for i in range(len(gas)): diff gas[i] - cost[i] total diff cur diff if cur 0: start i 1 cur 0 return start if total 0 else -1第一部分算总账。把所有站的gas减cost加起来如果总和小于0说明整条路的油量供应不足直接返回-1。这个判定是全局性的也是必要条件。第二部分确定起点。从0开始模拟维护一个cur变量表示当前累计的剩余油量。当cur小于0时说明从当前start到i之间的任何站点都不能作为起点因为从任何一个站点出发走到i这里油都会耗尽。因此直接把起点重置为i1cur归零重新累计。为什么“从start到i之间任何站点都不能作为起点”这一点是很多人卡住的点。假设起点是jstart j i从j出发的剩余油量可以看作从start出发到j时已有的油量再加上j到i这段的增量。既然从start出发到i时总量为负那么任意j到i的子段也至少有一个点是负的也就是说会在i或i之前断油。所以直接跳过整个区间从i1重新尝试是安全的。这个结论很反直觉但配合一个例子就清楚了。用gas [1,2,3,4,5], cost [3,4,5,1,2]手动推一遍从0开始diff数组是[-2, -2, -2, 3, 3]cur在前三站就变成-6start跳到3cur重置3453, 33-1-23走完整圈。结果返回3正确答案。3. 实操心法怎么判断一道题能不能贪心以及怎么证明3.1 三个信号帮你快速锁定贪心刷题量上来以后我判断一道题能不能用贪心基本看三个信号。第一题目问的是“最大值”“最小值”“是否可行”“最少次数”这类极值或判定问题。这是贪心的常见出题面。如果是“求所有方案中满足条件的那一个”或者“求具体方案数量”那大概率是回溯/DP而不是贪心。第二决策的每一步不会改变后续可选集合的结构只改变一个单调推进的量。比如55题和763题核心都是维护一个不断向右推进的边界前面的决策不会“绕回去”影响边界上限。一旦你发现前面的选择会改变后面状态的计算方式比如背包问题里选不选当前物品会影响剩余容量那贪心就危险了应该考虑DP。第三题目存在一个明显的“排序/取最值”先手动作。比如活动选择按结束时间排序122题按相邻差价取正134题找第一个油量为负的断点。这类题十有八九是贪心。满足这三个信号先按贪心写写出来样例过不了再换DP或者回溯。这个流程在面试时非常高效因为大多数面试官期待的就是你先判断题型再动手而不是上来就写状态转移。3.2 交换论证面试现场证明贪心正确性的实用方法很多人面试时能写出贪心解法但被问“为什么这样是对的”就卡壳。这里分享一个最实用的证明工具交换论证法。核心思想是假设存在一个最优解如果这个最优解的第一步或某个位置和我们贪心选择的方案不一样通过交换它们最优解不会变差。反复交换后最优解就变成了贪心解。拿活动选择举例。假设存在一个最优解第一个选择的活动不是结束时间最早的A而是另一个活动B。由于A结束时间不晚于B把B换成A后A占用的时间区间不会超过B因此后续所有活动依然可以和A搭配。这样得到的解仍然是一个合法解活动数量没有减少。既然如此最优解完全可以被改造成一个“第一步就是贪心选择”的解。接着对后续步骤做同样的交换最后就得到贪心解。所以贪心解就是最优解。面试时不要求你写出严格的数学证明能把交换论证的逻辑说清楚就够用了。这比背一堆结论强得多——因为题目一变结论就失效但证明逻辑能复用。3.3 推荐刷题顺序从易到难的梯度安排如果时间有限我的建议是严格按照这个顺序刷先做121再做122。感受“一次交易拆成无限次交易”的思维跳跃再做55再做45。感受“可不可达”和“最少步数”的差异然后做763训练“区间边界维护”的模型最后做134因为它带有环形数组和数学结论是这几道里最需要推理的一题。整体节奏上这些题如果每天投入两小时三天内可以全部吃透。但“吃透”的定义不只是AC而是每道题都能不看题解重新推一遍并且能用自己的话讲清楚贪心策略为什么正确。做完这一步你面对面试里绝大多数贪心题至少能快速判断出“这题能不能贪”了。4. 高频问题与翻车现场这些坑我替你踩过了4.1 贪心和动态规划怎么区分很多题其实两解我见过最多的疑问就是“这题我用了DP怎么题解里说是贪心”。这两者的关系不是互斥的。贪心是DP在满足“贪心选择性质”时的一种特例剪掉了大量状态只用最优状态推进。DP则是把可能的状态全部保留下来用状态转移保证最优。区分它们有个简单套路决策时如果我只需要知道“当前最优的一个值”不需要知道“所有可能的值”那就是贪心如果每一步都需要保留多种状态比如背包问题里容量不同导致结果不同那就是DP。121题两种方法都能解用“记录历史最低价当前利润”就是贪心视角定义dp[i]为第i天卖出的最大利润再做转移就是DP视角。两种解法的复杂度一样但思维方式不同面试时你能说清任意一种都行。4.2 腐烂的橘子为什么不算贪心先把题型标签认清楚“力扣腐烂的橘子是什么题型”这个问题经常出现在力扣相关搜索热词里。说清楚994题腐烂的橘子属于多源BFS不是贪心。原因在于它求的是“所有橘子腐烂需要的最少分钟数”这个分钟数由扩散层数决定。BFS天然逐层扩散每扩散一层就是一分钟所以BFS就是最契合的解法。贪心在这里没有用武之地——因为每一分钟扩散的源头是多个选择哪个橘子先腐烂并不会改变扩散速度不存在“局部最优决策点”。这个题也提醒我们刷题时别只看题目问“最少/最长”就默认是贪心先想想问题的结构适不适合逐层模拟或者图论遍历。4.3 边界条件与细节坑三道题里的典型错误以下几个坑是我以及身边很多人在刷这几道题时真实踩过的整理出来方便自查55题和45题在nums长度为1时前者直接返回True后者直接返回0。很多思路版本没做这个特判会导致循环逻辑额外跳一次。45题里的cur_end和farthest更新顺序很容易写反。正确顺序是先不断更新farthest等到i撞到cur_end时再步数1并把cur_end设为farthest。如果一开始就把cur_end更新了后面i就永远撞不到边界了。134题容易忘记total的全局判断。有些人只做了局部模拟当某个局部cur小于0时重置start最后直接返回start其实如果total 0这个start是走不完一圈的。所以必须先有total 0这个前提或者最后返回前再判断一次。763题要注意start重置的位置。切完一个片段后start应该设为end 1而不是end。这个错误我在白板面试时犯过一次非常尴尬。这些小细节单独看都不难但组合起来就是“样例过、提交挂”的重灾区。所以刷这些题时我建议刻意多准备几组边界用例来验证空数组、单元素数组、全相同字符、全零数组等。我个人刷完这组题之后的体会是贪心很少考智商更多是考模型积累。你见过“维护最远边界”这个模型45题就是送分题没见过可能想半小时都对着样例发懵。所以建议把这六道题当成模板题来背但背的不是代码而是“为什么这个局部选择是安全的”那段论证逻辑。等你把这个问题想明白了hot100里的贪心部分就算真正过关了。