Hot100刷到贪心专题这组题时我的第一反应是终于有一个专题能靠“拍脑袋”解题了。但真上手之后才发现贪心在热题100里恰恰是最考验“判断力”的一块——很多题一眼看过去像是贪心写出来也能过一半样例可就是有那么几个边界case卡得你怀疑人生。这个专题对应的题目数量不算多但覆盖的模型很杂有区间调度、跳跃游戏、股票买卖、前后约束、环形数组还有带排序的贪心。如果你正在刷Hot100我强烈建议把贪心单独拎出来做一次专项整理因为它比动态规划更依赖直觉验证又比分治、回溯更容易出现“想当然”。这篇就把我反复折腾后的理解写出来从题单梳理到五个高频模型的拆解再到怎么判断一道题到底能不能贪心最后附上一些踩坑记录给你一个可以直接照着用的刷题路径。1. 贪心专题在Hot100里的“位置感”1.1 为什么说贪心题“看起来简单做起来容易翻车”贪心算法的定义很朴素每一步都做当前看起来最好的选择期望最后得到全局最优。这个思想我们生活中天天在用比如买菜挑最新鲜的、赶路选当前最快的车道。但算法题里的贪心不是“拍脑袋”它要求你证明“局部最优能推出全局最优”。最经典的反例是0-1背包每一步都选单位价值最高的物品最后可能因为装不下而浪费容量全局反而不优。Hot100里的贪心题藏得比较深很少直接给你一个裸的“每次取最大”的题而是把贪心嵌在排序、双指针、模拟里导致很多人在读题阶段就判断错了方向。我自己的体会是贪心专题在Hot100里更像一个“判断题”你不仅要会写某种贪心策略还要能快速识别哪些题能用贪心哪些题看起来像但实际要用动态规划。比如买卖股票有两道题121题是只能买卖一次122题是能买卖多次。前者用贪心就会错后者用贪心才能过。这种“同题材不同解法”的对比恰恰是刷Hot100最有价值的地方。1.2 Hot100中公认的贪心题单与分类以我刷到的Hot100版本为例涉及贪心思想的核心题大概有下面这些。我先按模型分个类方便后面逐个拆题号题目贪心切入点模型分类55跳跃游戏维护能跳到的最远位置跳跃/可达45跳跃游戏II在每段可跳范围内选下一步最远位置跳跃/最少步数122买卖股票的最佳时机II每天只要有差价就累加股票/增量134加油站总油量判断可行累计余量最低点后为起点环形/累计余量135分发糖果两次遍历处理两个方向的比较关系前后约束406根据身高重建队列按身高降序、k升序后逐个插入排序插入621任务调度器按任务频次安排冷却时间频次/桶思想763划分字母区间记录每个字母最后出现位置扫描切分区间边界435无重叠区间按右端点排序尽量选结束早的区间区间调度452用最少数量的箭引爆气球按右端点排序合并重叠区间区间调度当然不同版本的Hot100收录题号会有出入比如有的版本把435、452收录有的版本则没有。这不重要重要的是这些题目背后的贪心模型是相通的你在任何一个版本里把它们啃透遇到其它区间题、跳跃题都能迁移。2. 五类高频贪心模型的拆解2.1 区间调度终点排序是万能的起点区间类问题是我在Hot100里最先搞定的因为它套路最固定。拿435“无重叠区间”来说题目要求移除最少数量的区间使剩余区间互不重叠。很多人的第一反应是按区间起点排序然后依次判断重叠。这个思路不能说完全错但很容易踩坑按起点排序后如果一个区间跨度特别大它会挡住后面很多区间贪心选择它会导致需要移除更多区间。正确的做法是按右端点排序。为什么因为结束得越早的区间给后面留下的空间越大。这个道理和生活中安排会议室一样如果一个会议最早结束那就优先安排它后面能塞进的会议最多。按右端点排序后从左到右扫描维护当前已选区间的最右端点preEnd。每次遇到新区间如果它的左端点大于等于preEnd说明不重叠选它并更新preEnd如果重叠就丢弃这个区间同时把移除数量加一。以435为例Python的写法很简洁def eraseOverlapIntervals(intervals: List[List[int]]) - int: if not intervals: return 0 intervals.sort(keylambda x: x[1]) # 按右端点排序 pre_end intervals[0][1] removed 0 for i in range(1, len(intervals)): if intervals[i][0] pre_end: # 不重叠 pre_end intervals[i][1] else: removed 1 return removed注意题目里“边界接触”算不算重叠要看具体描述。435里[1,2]和[2,3]不算重叠所以用的是。452“引爆气球”里两个气球只要x_start x_end就算重叠因为箭可以正好射在边界上所以判断条件要写成intervals[i][0] pre_end才需要新箭。读题时这个细节直接影响代码千万别想当然。再说说56“合并区间”它是区间题的另一个变体这次不是移除重叠区间而是把重叠的合并成一个。合并场景反而更适合按左端点排序然后遍历时不断更新当前合并区间的右端点。这两道题放在一起刷你就能明显感受到“排序维度不同结果完全不同”的微妙之处。2.2 跳跃游戏维护“最远可达距离”的边界感55题“跳跃游戏”是贪心入门的必做题。题目给一个数组每个元素表示从当前位置最多能跳多远问能不能跳到最后一个下标。最简单的贪心策略是维护一个max_reach变量表示目前能到达的最远位置。遍历每个下标时如果当前下标还在max_reach范围内就用i nums[i]更新max_reach。一旦max_reach大于等于最后一格立刻返回True。这里容易犯的一个错误是不注意“当前下标是否可达”的判断。很多人上来就写max_reach max(max_reach, i nums[i])完全不看这个位置能不能走到。如果中间某个位置不可达那它后面的所有更新就都失去了意义。正确写法如下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]) if max_reach len(nums) - 1: return True return True45题“跳跃游戏II”是它的加强版要求跳到最后一格的最少步数。这里的贪心策略要稍微进阶一点不是每走一步都选跳得最远的位置而是在当前这一段“能到达的范围内”选择下一步能延伸到最远的位置。实现时用两个变量current_end表示当前步数能覆盖到的边界farthest表示在这个边界内所有位置可以达到的最远距离。遍历时不断更新farthest当i走到current_end说明必须跳一步了这时把步数加一并把current_end更新成farthest。def jump(nums): if len(nums) 1: return 0 steps 0 current_end 0 farthest 0 for i in range(len(nums)): farthest max(farthest, i nums[i]) if i current_end: steps 1 current_end farthest if current_end len(nums) - 1: break return steps这段代码的边界感很强必须遍历到current_end才加步数不能在更新farthest时立刻加。我第一次写的时候就是这里搞反了导致每一步都会被重复计数。后来在纸上画了个例子才明白当前步数的“覆盖范围”就像一个波次每到一个波次的末尾才发动下一次跳跃而不是每看到一个更远的位置就跳。2.3 股票买卖把差价拆成每天的增量122题“买卖股票的最佳时机II”允许无限次交易但手里只能持有一只股票。这道题的贪心策略看起来甚至有点“无脑”只要今天价格比昨天高就认为昨天买入、今天卖出赚到这段差价如果今天比昨天低或持平就不操作。把所有正差价累加起来就是最大利润。为什么这个“无脑”策略是对的因为不限交易次数时一段从低价到高价的上涨它的总收益等于每天相邻差价的累加。比如价格是[1,3,5]从1买5卖收益4等价于(3-1)(5-3)224。所以只要每天有价差就赚相当于捕捉了每一个上涨波段。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但同样的思路放到121题“买卖股票的最佳时机”就会出错。121题只能买卖一次如果天天做差价相当于多次交易违背题意。121题的经典解法是遍历时记录历史最低价格然后算“当前价减历史最低价”的最大值这其实是一种“扫描”思想不是严格的贪心。这两道题放在一起特别能说明问题同一个股票模型交易次数限制一变算法就变了刷题时一定要先看清题目条件。2.4 前后遍历分发糖果的两遍扫描法135题“分发糖果”是Hot100里比较有名的一道题。每个孩子至少一颗糖相邻两个孩子中评分高的必须比评分低的糖多问最少需要多少颗糖。这里的约束其实是由两个方向的不等式组成的从左往右看右边的孩子评分高就要比左边多从右往左看左边的孩子评分高就要比右边多。很多人的第一反应是扫描一遍看到相邻逆序就加糖。但只扫一遍很难同时满足两个方向。正确解法是拆成两次遍历先从左到右保证每段上升序列中右边的糖比左边多再从右到左保证下降序列中左边的糖比右边多。第二次遍历时每个位置取当前值和右边值加一中的较大者因为要同时满足两边约束。def candy(ratings): n len(ratings) candies [1] * n # 从左到右 for i in range(1, n): if ratings[i] ratings[i-1]: candies[i] candies[i-1] 1 # 从右到左 for i in range(n-2, -1, -1): if ratings[i] ratings[i1]: candies[i] max(candies[i], candies[i1] 1) return sum(candies)这里要注意第二次遍历为什么是max而不是直接赋值。如果直接赋值成candies[i1] 1可能会把左边遍历得到的结果覆盖掉导致左边约束被破坏。取最大值才能同时兼容两个方向的约束。这个“两次遍历 取max”的套路其实在很多涉及“同时满足两个方向约束”的题里都能用属于可以迁移的模型。2.5 环形问题加油站的总油量思维134题“加油站”是Hot100里少见的环状贪心。题目给两个数组gas[i]表示在i号加油站能加的油cost[i]表示从i开到下一站消耗的油。问从哪个加油站出发能绕着环路走一圈如果不存在返回-1。这道题的贪心解法很简单但理解起来有点绕。第一步计算总油量和总消耗。如果sum(gas) sum(cost)那无论从哪出发都跑不完直接返回-1。第二步遍历数组用一个current_tank记录从当前候选起点到当前位置的剩余油量。当current_tank变成负数说明当前候选起点不行把起点设为下一站并把current_tank重置为0。遍历结束后记录的起点就是答案。def canCompleteCircuit(gas, cost): total 0 current 0 start 0 for i in range(len(gas)): diff gas[i] - cost[i] total diff current diff if current 0: start i 1 current 0 return start if total 0 else -1为什么这样做是对的可以换个角度理解从候选起点出发如果把某个点作为分界前面累计剩余油量出现了全局最小值那么起点应该在这个“最亏”的位置之后。因为环路上任意一点作为起点其他点相对于这个起点的累计剩余量都会整体平移而只有从最低点之后出发才能保证全程累计剩余量都在0以上。我一开始记不住这个结论后来用画折线图的方式才彻底搞懂把每站的“净增油量”累加画出来从累计最低点的下一站出发折线整体被抬高了不会再冲到0以下。3. 怎么判断一道题能不能贪心3.1 贪心选择性质与最优子结构的最小白话版学算法导论时贪心这章最绕的就是两个概念贪心选择性质和最优子结构。用大白话说贪心选择性质就是“你这一步做了某个局部最优选择之后还能继续用同样的方式得到全局最优不需要回头修改”。最优子结构就是“整体最优解里去掉第一步之后剩下的部分对剩余子问题来说也是最优解”。判断一道题能不能贪心最简单的方式是反着想我做了这个局部最优决策之后会不会导致后面某个环节“打死也补不回来”如果会导致那就不适合贪心。比如找零钱问题在硬币面额为1、5、11的体系下要凑15元贪心会先拿11剩下4需要四个1总共5枚但最优是555只要3枚。为什么贪心失效因为面额之间没有倍数关系局部大面额的选择堵死了后面用中等面额组合的可能性。另一个判断标准是看题目是否具有“单调性”或“可交换性”。区间调度里最早结束的区间和任意其他最早开始的区间交换不会让结果更差股票买卖里相邻差价累加不会受其他交易影响。这些能通过“交换论证”的题基本都可以放心贪。刷Hot100时我遇到一道题会先在心里问一句如果这一步选了当前最优后面的最优解会不会因此被破坏如果不会就往贪心方向写。3.2 几个容易误用贪心的反例我建议每个刷贪心专题的人都准备一个“贪心失效”的笔记本里面至少有这几个经典反例第一个是0-1背包。分数背包可以按单位重量价值排序一直装因为物品可以切割不会浪费空间但0-1背包不行装下一个大块头可能挤掉好几个小块头。Hot100里虽然没有直接的0-1背包题但它的变体会以“能否组成目标”的形式出现比如416“分割等和子集”那个要用动态规划。第二个是找零钱。前面提到的硬币面额1、3、4凑6元贪心会选411共3枚实际33才是2枚。这个反例告诉我们贪心的“局部最优”依赖于货币面额的性质不能套到任意面额上。第三个是最短路径。Dijkstra算法本质上是一种贪心每次选当前距离最小的未访问节点。但一旦图中出现负权边当前最小距离可能被后面的负边进一步减小贪心就失效了必须换Bellman-Ford。Hot100里的单源最短路径题不多但理解这个例子能帮你建立“贪心有前提条件”的意识。4. 常见错误、排查技巧与面试心法4.1 五个最容易踩的坑我把刷题过程中反复踩的五个坑整理成了一张表如果你也碰到WA优先对着表检查坑位典型场景正确操作排序方向选错区间题到底按起点还是终点排序求“最多不重叠区间”按终点求“合并区间”按起点边界是否重叠没看清[1,2]和[2,3]算不算重叠题目说“接触不算重叠”用气球题用忘了判断“当前位置可达”跳跃游戏直接更新最远距离先判断i max_reach就返回False更新步数时机不对45题在遍历每个位置时都加1必须在到达current_end时才加1两次遍历时直接覆盖结果135题第二次遍历不取max第二次要用max(candies[i], candies[i1]1)最后一个坑尤其隐蔽。我写135题时第一次只做了从左到右的遍历样例全过了提交却挂在一个很长的用例上。那时才意识到只扫一遍根本无法处理“左边评分高、右边评分也高”的波峰。后来改成两遍扫描并取max才把所有情况覆盖住。4.2 刷题调试实录从WA到AC的排查路径有一次我在45题上卡了很久写出来的代码总是比答案多一。我的调试方法很简单先用暴力DFS或动态规划写一个正确的baseline然后用随机小规模数据对比贪心结果。这个习惯我强烈推荐它能让你快速定位到贪心策略失效的“临界点”。那次我构造了nums [2,3,1,1,4]正确的答案是2步从0跳到1再从1跳到4。但我写的代码却输出3步。对照baseline后我发现问题出在我把“步数加一”的时机放在farthest更新的地方了。我一开始的代码在遍历到位置1时发现farthest变成了4于是立刻把步数加一但实际上这时还在第0步的“覆盖范围”内不应该加步数。后来改成if i current_end才加步数代码就对了。这个经历让我总结出一条调试心得遇到贪心题WA不要急着换策略先检查“决策时机”和“决策范围”是不是搞混了。很多时候策略没问题只是你让贪心“行动”的时机早了一步或晚了一步。4.3 面试现场怎么快速定位贪心策略面试场景下没有编译器反复试错所以需要在几十秒内形成判断。我的习惯是看三点第一看数据范围。如果n给到10^5甚至更大通常不是动态规划除非是O(n)级别的DP也不是回溯因为状态空间太大。这时候优先考虑贪心、排序、双指针或二分。第二看题目问法。出现“最多/最少”“能否达到”“最少步数”“最大利润”“最小数量”这类词如果模型又比较“直观”大概率有贪心解法。第三看局部决策对后续的影响。如果是“选了一个之后剩下的问题结构和原来一样只是规模变小”那就可以尝试贪心。面试时还有个沟通技巧你可以先抛出一个贪心假说然后主动和面试官说要验证两个性质——贪心选择性质和最优子结构。不需要在线写严格证明只要你能举出“为什么这个局部最优不会堵死后路”的关键理由面试官通常会认可。如果你发现自己在试图证明时找不出原因那大概率这个题不是贪心赶紧转DP。最后补充一点个人经验Hot100的贪心专题其实不需要刷太多题把那十来道题反复刷三遍比盲目刷五十道新题更有效。我每刷完一轮会在注释里写清楚“为什么能贪心”和“如果贪心会挂在哪里”下次再遇到类似的题直接翻笔记对照模型。贪心不是靠记忆题型而是靠建立“决策敏感度”——当你看到一个变量能下意识想到它是否值得维护、何时更新、怎么排序这个专题就算真正吃透了。