刷算法题刷到一定量你会发现一个规律LeetCode Hot 100 里真正算得上“纯贪心”的题目并不多大概在十道左右但这十道几乎覆盖了面试中最常出现的贪心模型——跳跃类、股票类、区间类、条件分配类。贪心算法在面试里是个很特别的存在代码往往短到可以直接默写可一旦场景换了你盯着屏幕五分钟都可能不知道这一步到底该“贪”什么。这篇文章我会围绕 Hot 100 里的原题把每一道题的贪心切入点、代码实现以及背后的正确性理由拆开讲同时把“这道题凭什么能贪”的判断方法也一并说清楚。适合正在准备算法面试、刷过题但遇到新题还是没思路的读者也适合想从题目反推贪心本质的进阶选手。1. 贪心算法在 Hot 100 里的分布与定位——先看清楚对手1.1 Hot 100 中哪些题在考贪心我把目前 Hot 100 里常被归类为“贪心类”的题目整理了一遍先给你一张清单。需要说明的是不同版本的 Hot 100 题单有细微出入但核心的几道基本固定。你在刷题时如果看到下面这些题可以默认要求自己用贪心思路去做一遍而不是直接套动态规划。题号题目难度贪心切入点55跳跃游戏中等维护最远可达位置判断是否存在断路45跳跃游戏 II中等按当前覆盖区间边界推进记录最少步数121买卖股票的最佳时机简单记录历史最低点计算当前最大差价122买卖股票的最佳时机 II中等累加所有正差等价于捕捉每段上升区间134加油站中等汽油总量为负则全局无解当前油量最差处重置起点135分发糖果困难把“两边都要满足”拆成两次单向遍历435无重叠区间中等按右端点排序每次保留最早结束的区间452用最少数量的箭引爆气球中等按右端点排序一支箭尽可能覆盖更多气球763划分字母区间中等记录每个字母最后一次出现的位置406根据身高重建队列中等身高降序、相同身高按人数升序依次插入56合并区间中等排序后线性合并严格说更偏排序模拟上表里 406 和 56 我标了“更偏排序”但面试中你完全可以按贪心的思路去分析排序顺序为什么合理。尤其是 406它前面的排序策略本身就是“为了让后续插入时不再被高个子干扰”这其实是贪心选择的体现。1.2 贪心题在面试中的出题逻辑与定级为什么面试官明知道贪心容易跟动态规划混在一起还是爱出这类题我的观察是贪心题代码量小评讲起来不费时间但足够考察一个人能不能在 O(n) 或 O(n log n) 级别内解决问题同时还能区分“背过模板”和“真懂原理”的人。常见的定级思路是这样的如果题目满足“每步做局部最优选择之后不需要回退修正”这个特征通常就是贪心题。比如买股票你在每个时刻只需要记住当前之前的最低价格然后用当前价格减一减根本不需要回头看。再比如区间调度你只需要持续选择“结束最早”的区间因为留给后面的空间最大。面试官如果看到你上来想的是“状态转移方程”而题目其实可以在线性时间内解决往往就会在提示词里引导你回到贪心方向。一个容易掉进去的陷阱是把贪心题目里的“排序”环节当成题目重点。排序只是给局部比较建立确定性真正的难点是排序规则本身。你如果能把 435、452、763 的排序规则放在一起对比就基本掌握了区间类贪心的套路这也是我后面单独开一章的原因。2. 从“跳跃游戏”到“跳跃游戏 II”贪心策略的逐步升级2.1 跳跃游戏55能不能跳到的核心判断55 题的题意是每个位置的数字表示你最多能往前跳多远问能不能从下标 0 跳到最后一个下标。最容易想到的思路是 DFS 或者动态规划但你会发现 DFS 会超时DP 的复杂度也不是最优。这道题真正的贪心解法是维护一个变量 maxReach代表当前已经走过的位置中最远能到达的下标。代码一点都不复杂def canJump(self, nums: List[int]) - bool: 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 True我见过不少初学者卡在这个问题上的原因是他们总是想具体模拟“走哪条路”。但贪心的核心恰恰是不关心你具体落在哪个位置只关心“从我踏过的所有位置出发最远能到哪”。如果最远可达位置都到不了某个点那从任意一个更近的位置出发也永远到不了那个点。这个逻辑可以用反证法验证假设存在一条路径能越过断层那它必然在某一步从某个已到达的位置跳得更远这与“maxReach 是已到达位置的最大跳跃范围”矛盾。所以维护最远可达距离这个贪心选择是安全的。55 题还有一个很常见的变体问“最少跳几次”就是下一道 45 题。建议你在学 55 的时候顺便把 45 拿过来对比做因为它们的底层思想同源但 45 多了一个边界记录技巧不是简单地套一个 counter 就行。2.2 跳跃游戏 II45最少步数的贪心区间推法45 题要你在保证能到达终点的基础上求出最少的跳跃次数。这里的贪心策略变成了“每次跳到当前覆盖范围内能让你下一步跳得更远的那个位置”。但代码实现上有一个更精妙的写法不必真正计算从哪个点起跳而是维护当前一步的覆盖右边界 curEnd以及下一步能达到的最大范围 maxReach。当遍历下标等于 curEnd 时说明这一步的覆盖范围已经全部扫过必须再跳一次。def jump(self, nums: List[int]) - int: n len(nums) cur_end 0 max_reach 0 steps 0 for i in range(n - 1): max_reach max(max_reach, i nums[i]) # 已经走完当前步的最远覆盖边界必须起跳 if i cur_end: steps 1 cur_end max_reach if cur_end n - 1: break return steps用一个例子跑一遍会更清晰。假设 nums [2, 3, 1, 1, 4]一开始 cur_end 0、max_reach 0。i0 时max_reach 更新为 2此时 i cur_end说明初始位置已经走完steps 变 1cur_end 变 2。i1 时max_reach 更新为 max(2, 13)4i2 时max_reach 保持 4此时 i cur_endsteps 变 2cur_end 变为 4已经可以覆盖终点循环结束。整个过程中你发现cur_end 就像一个“一段一段往前推进的窗口”每一段结束时步数加一而 max_reach 负责在窗口内不断收集未来能覆盖的更远位置。这个写法的正确性基于一个关键事实在你遍历到 cur_end 的过程中max_reach 累计的是“当前这一段内任意一点起跳”的最远距离。既然这一段内所有点都已经看过了那最优的下一步一定是从其中某个点跳到 max_reach步数只加一就够了。你不需要关心具体从哪一点跳因为所有候选点的信息都被 max_reach 压缩掉了。这一点也是很多讲解视频没讲透的地方为什么每次 i 走到 cur_end 就加一步因为 cur_end 是当前步的极限覆盖边界你不可能不跳就跨过它。3. 股票系列跨题串联理解贪心的“局部最优”3.1 买卖股票最佳时机121一次交易中的极值跟踪121 题要求你只能买卖一次求最大利润。最容易想到的是暴力枚举买入日、卖出日复杂度 O(n²)在题目数据范围下会超时。贪心解法只需要一趟遍历记录遍历到当前天为止的最低买入价然后拿今天的价格减去这个买入价更新最大利润。def maxProfit(self, prices: List[int]) - int: min_price float(inf) max_profit 0 for price in prices: min_price min(min_price, price) max_profit max(max_profit, price - min_price) return max_profit这里“贪”的点非常直观如果已经决定在某个价格卖出那买入价当然是越低越好。所以每个卖出日的“局部最优解”就是当前历史最低点。你可能会想这不是理所当然的吗对贪心题就是这样——有时候一个看起来显然的策略就是全局最优解。难点在于你敢不敢用它来替代 DP。我在准备面试时喜欢把这道题和“最大子数组和”放在一起看因为它们维护的都是“到当前位置为止的最优前缀信息”。121 维护的是历史最低价实际上就是在比较每个位置作为卖出点时历史前缀中最优的买入点。区别只在于 121 的利润依赖于价格差而最大子数组和直接累积和。理解这层关系后股票题就不是单独一题而是一个“前缀极值”模型。3.2 买卖股票最佳时机 II122把每段上升都吃掉122 题把限制放宽成了可以多次买卖但要求不能同时持有多股也就是手上最多留一股。直觉上你会觉得应该“低买高卖”但到底怎么决定每次买卖的时机有一个极其简单又极其容易让人怀疑的解法只要今天的价格比昨天高就在昨天买、今天卖把所有这样的正差价累加起来。def maxProfit(self, prices: List[int]) - int: total_profit 0 for i in range(1, len(prices)): if prices[i] prices[i - 1]: total_profit prices[i] - prices[i - 1] return total_profit很多人第一次看到这个解法的反应是如果价格是 1、2、3第一天买第三天卖能赚 2而按这个算法会赚2-13-22结果一样。那如果价格是 1、3、2、5算法会算 2 3 5确实等于 1 买 3 卖赚 2再 2 买 5 卖赚 3的总和。但有人会追问为什么不直接在 1 买、5 卖一口气赚 4因为题目限制你手里最多只有一股你在 1 买 5 卖期间错过了 3 到 2 的那段回落吗不会因为你只要在 3 卖掉避开 2 的下跌再在 2 买回来总利润反而变成 5。所以这道题的贪心本质可以理解成不预测未来只捕捉每一个正的增长区间负的区间全部跳过。从数学上看总利润等于相邻价格差的非负部分之和而任何“跳着买卖”的方案都能被拆成若干相邻差值的累加其中负差部分只会拖累总收益所以保留所有正差就是最优。4. 区间问题三件套排序、贪心、背靠背验证4.1 无重叠区间435最小删除数的排序策略435 题给定一堆区间要求删除最少的区间让剩下的区间互不重叠。正向思维是“删除最少”逆向思维则是“保留最多”。只要保留了尽可能多的不重叠区间删除数自然最少。这时候贪心策略就变成了经典的区间调度将所有区间按右端点升序排序然后依次扫描能保留就保留。def eraseOverlapIntervals(self, intervals: List[List[int]]) - int: intervals.sort(keylambda x: x[1]) prev_end float(-inf) keep 0 for start, end in intervals: if start prev_end: keep 1 prev_end end return len(intervals) - keep为什么一定按右端点排而不是左端点这里的关键是右端点更早的区间给后续区间留下了更大的剩余空间。如果你按左端点排可能先保留一个区间虽然开始得早但结束得晚直接挡掉后面好几个区间。我可以举一个反例来说明区间 [1, 100]、[2, 3]、[4, 5]按右端点排会先保留 [2, 3] 和 [4, 5]删除 [1, 100]这是最优解按左端点排会先处理 [1, 100]导致只剩一个区间。所以这道题的“贪心选择性质”是在一个区间片段中选择右端点最小且不与已选区间重叠的区间永远不会比选择其他区间更差。这就是典型的交换论证——任何不是按这个策略选出来的最优解都可以被调整成这种形式而不会让结果变差。4.2 引爆气球452右端点排序的贪心证明452 题是 435 的姊妹题但问法换成了“用最少的箭引爆所有气球”。每支箭射中一个位置后所有覆盖这个位置的气球都会被引爆。表面上是射箭问题实际上是要找最少个数的点使得每个区间都至少包含其中一个点。解法依旧按右端点排序第一支箭直接射在第一个气球的右端点上然后扫描所有气球凡是左端点小于等于当前箭位置的气球都可以被这支箭引爆直到遇到左端点在箭位置右边的气球才必须换一支新箭。def findMinArrowShots(self, points: List[List[int]]) - int: points.sort(keylambda x: x[1]) arrows 1 prev_end points[0][1] for start, end in points[1:]: if start prev_end: arrows 1 prev_end end return arrows这里注意和 435 的边界差异435 中不重叠的条件是 start prev_end而 452 中气球边界重合时还能共用一支箭所以只有 start prev_end 才需要新箭。我当年做这两题时就是在这一个大于等于号上栽过跟头把 435 的代码直接改改提交 452结果差了三个测试用例。从证明角度看你不需要真的证明为什么箭一定要射在某个气球的右端点上只需要理解一个核心逻辑第一个气球的右端点是所有右端点中最靠左的位置而任何一支能引爆第一个气球的箭都必须落在小于等于这个右端点的位置。为了让这支箭尽可能覆盖更多后续气球把它移动到第一个气球的右端点是最优的——移动后它能覆盖的气球集合不会变小反而可能变大因为右端点是所有可行位置里最靠右的一个会覆盖到更多左端点靠左的气球。4.3 划分字母区间763合并区间的变体763 题要求把字符串划分成尽可能多的片段同一字母只能出现在一个片段里。每个字母都要有一段完整的“生存域”所以你需要先知道每个字母最后出现的位置把问题变成一系列区间合并从头扫描字符串维护当前片段中所有字母的 last 值最大值当遍历位置等于这个最大值时就说明当前片段可以切断了。def partitionLabels(self, s: str) - List[int]: last {c: i for i, c in enumerate(s)} res [] start end 0 for i, c in enumerate(s): end max(end, last[c]) if i end: res.append(end - start 1) start end 1 return res你可以把这道题理解为“不重叠区间的贪心版”只不过区间不是一个一个显式给出而是从字符最后出现位置推导出来的。一个典型的错误是一上来就把每个字符的出现区间列出来然后套用 435 的解法。其实没必要因为本题要的是尽量多划分而字母区间之间天然没有重叠冲突你只需要保证“所有包含同一字母的区间不被切开”用一个滑动窗口边界加一即可。我觉得这道题的训练价值在于它提醒你很多区间类贪心题并不一定直接给区间数据可能需要你先做一次哈希表映射才能把问题抽象成区间。如果你在做题时发现一道题很像区间调度但数据表现是字符串或数组优先考虑“映射到区间”这一步。5. 两道味道独特的 Hot 100 贪心题分发糖果与加油站5.1 分发糖果135左右两次遍历的约束拆解135 题要求你给每个孩子发糖果满足两个条件每个孩子至少一颗相邻孩子中评分高的孩子必须比评分低的孩子拿得更多。想一次性同时满足左高、右高两个方向其实很绕正确的做法是把约束拆开用两次单向遍历分别处理。第一遍从左到右保证每个孩子如果比左边评分高糖果数就比左边多一颗。第二遍从右到左保证每个孩子如果比右边评分高糖果数就至少比右边多一颗。两次结果取最大值即可。def candy(self, ratings: List[int]) - int: 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[i 1]: candies[i] max(candies[i], candies[i 1] 1) return sum(candies)这道题容易被误判成“每次取局部最大值然后周围递减”之类的复杂模拟但其实核心认知是一个孩子最后拿到的糖应该同时满足“来自左侧约束的糖数”和“来自右侧约束的糖数”的较大者。正因为两次遍历分别只满足一个方向的约束它们各自都是贪心的从左往右时每一步只需要看左边这是局部最优从右往左时每一步只需要看右边同样是局部最优。最后取最大值合并两个约束并不会破坏任何一边的满足条件因为取最大值只会让糖果数增加不会违反“评分更高就拿更多”的原则。5.2 加油站134总和与累加的符号判断134 题是环形的你从某个加油站出发可以带无上限的油每到一个加油站会加油然后消耗固定的油量去下一站问能不能绕一圈并给出起点编号。先判断整体可行性把所有 gas[i] - cost[i] 加起来如果总和为负说明“总入账小于总消耗”无论如何都走不完全程。这一步实际上是整个贪心策略的“全局约束”。在总和不为负的前提下真正的贪心选择就藏在累加过程中维护一个当前油量 cur如果 cur 在到达某站时变成负数说明从当前起点 start 到这一站的任何一点都不可能作为有效起点。def canCompleteCircuit(self, gas: List[int], cost: List[int]) - int: total, cur, start 0, 0, 0 for i in range(len(gas)): total gas[i] - cost[i] cur gas[i] - cost[i] if cur 0: start i 1 cur 0 return start if total 0 else -1为什么 cur 为负时直接重置起点是安全的假设从 start 出发到站 i 时油量变负那么对任意介于 start 和 i 之间的站点 k从 k 出发到 i 时油量只会小于从 start 出发到 i 时的油量。因为从 start 到 k 这段路程中start 持有的初始油量是正贡献若你从 k 出发就白白丢掉了 start 到 k 这段积累的净油。因此中间所有站点都不可能作为可行起点直接跳到 i1 不会漏掉正确解。比较有意思的是这道题的“贪”甚至不需要证明“选局部剩余最大”之类的策略它仅仅是在证明“失败的路径可以整体排除”。这种排除式贪心在算法面试里很常见像“摩尔投票法”里的抵消操作也是同一类思维建议你把它们放在一起体会。6. 贪心正确性的证明套路与实战判定标准6.1 举反例是最快的排除手段面试时很多人怕答错一上来就闷头写代码。我给的建议是先在脑子里尝试举一个反例推翻自己的想法。每个贪心策略都可以被挑战“如果每次选当前最优有没有可能当前最优把未来最优的路堵死了”如果短时间内举不出反例而且你能隐约感觉到这个策略不会让后续选择空间变小那么它极有可能就是正确解法。我经常举反例来检验排序类贪心。比如 435 题如果有人提出“按区间长度从小到大排序贪心地选最短的区间”立刻可以用反例杀掉它区间 [1, 10]、[2, 3]、[3, 4]最短的两个区间是 [3,4] 和 [2,3]但它们互相重叠如果先选 [2,3]就选不了 [3,4]最终只能保留 2 个区间。但按右端点排序可以保留 [2,3] 和 [3,4]留下 [1,10] 被删除。一个反例就能说明问题比长篇大论更高效。6.2 三种常见证明方法交换论证、贪心选择性质、最优子结构在需要真正证明的时候我常用的有三种方式。第一种是交换论证Exchange Argument适合绝大多数“排序后贪心”的问题。思路是假设存在一个最优解 S它和贪心解 G 在前若干步的选择不一致然后通过交换 S 中某个选择为 G 的选择证明 S 不会变差最终可以把 S 变换成 G从而说明 G 不劣于任何最优解。452 题的证明就是这样第一支箭如果不在最左气球的右端点上把它右移到右端点覆盖的气球集合不会缩小。第二种是结合贪心选择性质与最优子结构进行归纳证明。贪心选择性质说的是“存在一个最优解其中第一步就包含贪心做出的选择”最优子结构则是“第一步完成后剩余子问题的最优解可以独立求解”。两者同时成立就可以归纳证明整个贪心策略正确。55 题就是一个典型最远可达距离是明显的贪心选择你选了它之后剩下的问题又是“从可到达的区域继续延伸最远距离”的子问题。第三种是数学归纳与反证结合的方式通常用来证明这类问题“如果某一步贪心选择错误那么任何最优解都可以被调整成贪心解且结果更好或相同。”我在面试中一般不会把完整证明念一遍因为时间不够最关键的是把交换论证的核心讲清楚再补一句“哪一个局部性质保证后续不受影响”面试官基本就会认可。6.3 Hot 100 里哪些题“看着像贪心”但其实是别的类别我踩过一个比较深的坑把“暴力模拟”和“贪心”搞混。比如合并区间56 题你虽然要排序但核心只是线性扫描合并每一步没有真正意义上的“最优选择”它更像模拟。而根据身高重建队列406 题排序后的插入过程也偏向模拟你可以说它有贪心味道但严格来说不要求证明最优选择。同样的Hot 100 里有些题像 70 爬楼梯、198 打家劫舍第一眼可能会想到“每次走两步最优”或“隔着偷最优”但实际上它们更稳妥的做法是动态规划因为局部最优组合不出全局最优。我的判断标准是如果贪心策略要求“每步只保留一个状态”但问题有明显的“选择分支影响后续”那就该用 DP。贪心是“我替所有未来选择做决定”DP 是“我把所有选择都试探一遍”。面试时如果你发现自己的贪心代码需要记录多个候选值那很可能是贪心不成立需要回头考虑 DP。7. 建议的刷题顺序与个人经验7.1 建议刷题顺序Hot 100 里的贪心题不必按题号刷按模型分类会更有效。我自己的顺序是先用 121 和 122 建立“局部最优叠加全局最优”的直觉再做 55 和 45 感受“覆盖边界推进”的贪心代码风格然后集中刷 435、452、763 这三个区间题因为它们之间只有微妙差别非常适合对比记忆。最后用 134 和 135 收尾这两道题对贪心正确性的理解要求更高做完之后你再看其他贪心题会轻松很多。如果你还想额外加练可以在平台里搜“贪心”标签挑几道中等难度但不在 Hot 100 的题比如会议室相关、分发饼干、最长递增子序列的非 DP 解法等进一步巩固交换论证的感觉。刷题时我强烈建议你给每道题写一句“贪心选择是什么”比如“55 题贪心选择是维护最远可达位置”“452 题贪心选择是把箭射在当前最左气球的右端点”这样复习时一眼就能回忆起来。7.2 面试中遇到贪心题的解题节奏面试遇到贪心题我建议按这个节奏走。先确认题目能不能排序不能排序的话观察有没有可维护的极值变量然后快速枚举几种可能的贪心策略并尝试举反例排除不安全的策略接着和面试官简短交流你选择的贪心策略用一两句话解释“为什么局部最优不会破坏全局”最后再写代码。很多候选人一上来就写代码写完才发现策略不对反而拉胯。先说“我打算按右端点排序每次都保留结束最早的区间因为这样能给后面留最大空间”面试官会给你正面反馈。写代码时我还有一个习惯先把边界情况想清楚。区间题的空数组、单元素数组跳跃题的长度为 1股票题的降序数组都是最容易掉分的地方。Hot 100 里的贪心题虽然代码短但测试用例非常毒宁可多写两个断言也别贪快。另外如果题目给出的数据范围很大贪心往往是面试官期待的方向因为 O(n) 或 O(n log n) 是最优的如果你发现自己写出了 O(n²) 的解法大概率不是这道题的正解。最后再说一点个人体会我刷完 Hot 100 里的贪心题之后最大的感受是贪心算法不是数学竞赛里的某种高深结构它本质上是在说“这个问题的结构足够好好到不需要后悔”。很多初学者觉得贪心靠直觉、看天赋其实不是它靠的是你见过足够多的模型并且能在几秒内判断“这个局部信息能不能代表所有候选”。建议你把这几道题反复刷三遍每遍都先独立复现贪心策略再对照证明。刷熟之后你会发现Hot 100 之外的大多数贪心题几乎都是这几类模型的排列组合。 LeetCode Hot 100贪心题全解析：跳跃、股票、区间模型与证明套路
刷算法题刷到一定量你会发现一个规律LeetCode Hot 100 里真正算得上“纯贪心”的题目并不多大概在十道左右但这十道几乎覆盖了面试中最常出现的贪心模型——跳跃类、股票类、区间类、条件分配类。贪心算法在面试里是个很特别的存在代码往往短到可以直接默写可一旦场景换了你盯着屏幕五分钟都可能不知道这一步到底该“贪”什么。这篇文章我会围绕 Hot 100 里的原题把每一道题的贪心切入点、代码实现以及背后的正确性理由拆开讲同时把“这道题凭什么能贪”的判断方法也一并说清楚。适合正在准备算法面试、刷过题但遇到新题还是没思路的读者也适合想从题目反推贪心本质的进阶选手。1. 贪心算法在 Hot 100 里的分布与定位——先看清楚对手1.1 Hot 100 中哪些题在考贪心我把目前 Hot 100 里常被归类为“贪心类”的题目整理了一遍先给你一张清单。需要说明的是不同版本的 Hot 100 题单有细微出入但核心的几道基本固定。你在刷题时如果看到下面这些题可以默认要求自己用贪心思路去做一遍而不是直接套动态规划。题号题目难度贪心切入点55跳跃游戏中等维护最远可达位置判断是否存在断路45跳跃游戏 II中等按当前覆盖区间边界推进记录最少步数121买卖股票的最佳时机简单记录历史最低点计算当前最大差价122买卖股票的最佳时机 II中等累加所有正差等价于捕捉每段上升区间134加油站中等汽油总量为负则全局无解当前油量最差处重置起点135分发糖果困难把“两边都要满足”拆成两次单向遍历435无重叠区间中等按右端点排序每次保留最早结束的区间452用最少数量的箭引爆气球中等按右端点排序一支箭尽可能覆盖更多气球763划分字母区间中等记录每个字母最后一次出现的位置406根据身高重建队列中等身高降序、相同身高按人数升序依次插入56合并区间中等排序后线性合并严格说更偏排序模拟上表里 406 和 56 我标了“更偏排序”但面试中你完全可以按贪心的思路去分析排序顺序为什么合理。尤其是 406它前面的排序策略本身就是“为了让后续插入时不再被高个子干扰”这其实是贪心选择的体现。1.2 贪心题在面试中的出题逻辑与定级为什么面试官明知道贪心容易跟动态规划混在一起还是爱出这类题我的观察是贪心题代码量小评讲起来不费时间但足够考察一个人能不能在 O(n) 或 O(n log n) 级别内解决问题同时还能区分“背过模板”和“真懂原理”的人。常见的定级思路是这样的如果题目满足“每步做局部最优选择之后不需要回退修正”这个特征通常就是贪心题。比如买股票你在每个时刻只需要记住当前之前的最低价格然后用当前价格减一减根本不需要回头看。再比如区间调度你只需要持续选择“结束最早”的区间因为留给后面的空间最大。面试官如果看到你上来想的是“状态转移方程”而题目其实可以在线性时间内解决往往就会在提示词里引导你回到贪心方向。一个容易掉进去的陷阱是把贪心题目里的“排序”环节当成题目重点。排序只是给局部比较建立确定性真正的难点是排序规则本身。你如果能把 435、452、763 的排序规则放在一起对比就基本掌握了区间类贪心的套路这也是我后面单独开一章的原因。2. 从“跳跃游戏”到“跳跃游戏 II”贪心策略的逐步升级2.1 跳跃游戏55能不能跳到的核心判断55 题的题意是每个位置的数字表示你最多能往前跳多远问能不能从下标 0 跳到最后一个下标。最容易想到的思路是 DFS 或者动态规划但你会发现 DFS 会超时DP 的复杂度也不是最优。这道题真正的贪心解法是维护一个变量 maxReach代表当前已经走过的位置中最远能到达的下标。代码一点都不复杂def canJump(self, nums: List[int]) - bool: 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 True我见过不少初学者卡在这个问题上的原因是他们总是想具体模拟“走哪条路”。但贪心的核心恰恰是不关心你具体落在哪个位置只关心“从我踏过的所有位置出发最远能到哪”。如果最远可达位置都到不了某个点那从任意一个更近的位置出发也永远到不了那个点。这个逻辑可以用反证法验证假设存在一条路径能越过断层那它必然在某一步从某个已到达的位置跳得更远这与“maxReach 是已到达位置的最大跳跃范围”矛盾。所以维护最远可达距离这个贪心选择是安全的。55 题还有一个很常见的变体问“最少跳几次”就是下一道 45 题。建议你在学 55 的时候顺便把 45 拿过来对比做因为它们的底层思想同源但 45 多了一个边界记录技巧不是简单地套一个 counter 就行。2.2 跳跃游戏 II45最少步数的贪心区间推法45 题要你在保证能到达终点的基础上求出最少的跳跃次数。这里的贪心策略变成了“每次跳到当前覆盖范围内能让你下一步跳得更远的那个位置”。但代码实现上有一个更精妙的写法不必真正计算从哪个点起跳而是维护当前一步的覆盖右边界 curEnd以及下一步能达到的最大范围 maxReach。当遍历下标等于 curEnd 时说明这一步的覆盖范围已经全部扫过必须再跳一次。def jump(self, nums: List[int]) - int: n len(nums) cur_end 0 max_reach 0 steps 0 for i in range(n - 1): max_reach max(max_reach, i nums[i]) # 已经走完当前步的最远覆盖边界必须起跳 if i cur_end: steps 1 cur_end max_reach if cur_end n - 1: break return steps用一个例子跑一遍会更清晰。假设 nums [2, 3, 1, 1, 4]一开始 cur_end 0、max_reach 0。i0 时max_reach 更新为 2此时 i cur_end说明初始位置已经走完steps 变 1cur_end 变 2。i1 时max_reach 更新为 max(2, 13)4i2 时max_reach 保持 4此时 i cur_endsteps 变 2cur_end 变为 4已经可以覆盖终点循环结束。整个过程中你发现cur_end 就像一个“一段一段往前推进的窗口”每一段结束时步数加一而 max_reach 负责在窗口内不断收集未来能覆盖的更远位置。这个写法的正确性基于一个关键事实在你遍历到 cur_end 的过程中max_reach 累计的是“当前这一段内任意一点起跳”的最远距离。既然这一段内所有点都已经看过了那最优的下一步一定是从其中某个点跳到 max_reach步数只加一就够了。你不需要关心具体从哪一点跳因为所有候选点的信息都被 max_reach 压缩掉了。这一点也是很多讲解视频没讲透的地方为什么每次 i 走到 cur_end 就加一步因为 cur_end 是当前步的极限覆盖边界你不可能不跳就跨过它。3. 股票系列跨题串联理解贪心的“局部最优”3.1 买卖股票最佳时机121一次交易中的极值跟踪121 题要求你只能买卖一次求最大利润。最容易想到的是暴力枚举买入日、卖出日复杂度 O(n²)在题目数据范围下会超时。贪心解法只需要一趟遍历记录遍历到当前天为止的最低买入价然后拿今天的价格减去这个买入价更新最大利润。def maxProfit(self, prices: List[int]) - int: min_price float(inf) max_profit 0 for price in prices: min_price min(min_price, price) max_profit max(max_profit, price - min_price) return max_profit这里“贪”的点非常直观如果已经决定在某个价格卖出那买入价当然是越低越好。所以每个卖出日的“局部最优解”就是当前历史最低点。你可能会想这不是理所当然的吗对贪心题就是这样——有时候一个看起来显然的策略就是全局最优解。难点在于你敢不敢用它来替代 DP。我在准备面试时喜欢把这道题和“最大子数组和”放在一起看因为它们维护的都是“到当前位置为止的最优前缀信息”。121 维护的是历史最低价实际上就是在比较每个位置作为卖出点时历史前缀中最优的买入点。区别只在于 121 的利润依赖于价格差而最大子数组和直接累积和。理解这层关系后股票题就不是单独一题而是一个“前缀极值”模型。3.2 买卖股票最佳时机 II122把每段上升都吃掉122 题把限制放宽成了可以多次买卖但要求不能同时持有多股也就是手上最多留一股。直觉上你会觉得应该“低买高卖”但到底怎么决定每次买卖的时机有一个极其简单又极其容易让人怀疑的解法只要今天的价格比昨天高就在昨天买、今天卖把所有这样的正差价累加起来。def maxProfit(self, prices: List[int]) - int: total_profit 0 for i in range(1, len(prices)): if prices[i] prices[i - 1]: total_profit prices[i] - prices[i - 1] return total_profit很多人第一次看到这个解法的反应是如果价格是 1、2、3第一天买第三天卖能赚 2而按这个算法会赚2-13-22结果一样。那如果价格是 1、3、2、5算法会算 2 3 5确实等于 1 买 3 卖赚 2再 2 买 5 卖赚 3的总和。但有人会追问为什么不直接在 1 买、5 卖一口气赚 4因为题目限制你手里最多只有一股你在 1 买 5 卖期间错过了 3 到 2 的那段回落吗不会因为你只要在 3 卖掉避开 2 的下跌再在 2 买回来总利润反而变成 5。所以这道题的贪心本质可以理解成不预测未来只捕捉每一个正的增长区间负的区间全部跳过。从数学上看总利润等于相邻价格差的非负部分之和而任何“跳着买卖”的方案都能被拆成若干相邻差值的累加其中负差部分只会拖累总收益所以保留所有正差就是最优。4. 区间问题三件套排序、贪心、背靠背验证4.1 无重叠区间435最小删除数的排序策略435 题给定一堆区间要求删除最少的区间让剩下的区间互不重叠。正向思维是“删除最少”逆向思维则是“保留最多”。只要保留了尽可能多的不重叠区间删除数自然最少。这时候贪心策略就变成了经典的区间调度将所有区间按右端点升序排序然后依次扫描能保留就保留。def eraseOverlapIntervals(self, intervals: List[List[int]]) - int: intervals.sort(keylambda x: x[1]) prev_end float(-inf) keep 0 for start, end in intervals: if start prev_end: keep 1 prev_end end return len(intervals) - keep为什么一定按右端点排而不是左端点这里的关键是右端点更早的区间给后续区间留下了更大的剩余空间。如果你按左端点排可能先保留一个区间虽然开始得早但结束得晚直接挡掉后面好几个区间。我可以举一个反例来说明区间 [1, 100]、[2, 3]、[4, 5]按右端点排会先保留 [2, 3] 和 [4, 5]删除 [1, 100]这是最优解按左端点排会先处理 [1, 100]导致只剩一个区间。所以这道题的“贪心选择性质”是在一个区间片段中选择右端点最小且不与已选区间重叠的区间永远不会比选择其他区间更差。这就是典型的交换论证——任何不是按这个策略选出来的最优解都可以被调整成这种形式而不会让结果变差。4.2 引爆气球452右端点排序的贪心证明452 题是 435 的姊妹题但问法换成了“用最少的箭引爆所有气球”。每支箭射中一个位置后所有覆盖这个位置的气球都会被引爆。表面上是射箭问题实际上是要找最少个数的点使得每个区间都至少包含其中一个点。解法依旧按右端点排序第一支箭直接射在第一个气球的右端点上然后扫描所有气球凡是左端点小于等于当前箭位置的气球都可以被这支箭引爆直到遇到左端点在箭位置右边的气球才必须换一支新箭。def findMinArrowShots(self, points: List[List[int]]) - int: points.sort(keylambda x: x[1]) arrows 1 prev_end points[0][1] for start, end in points[1:]: if start prev_end: arrows 1 prev_end end return arrows这里注意和 435 的边界差异435 中不重叠的条件是 start prev_end而 452 中气球边界重合时还能共用一支箭所以只有 start prev_end 才需要新箭。我当年做这两题时就是在这一个大于等于号上栽过跟头把 435 的代码直接改改提交 452结果差了三个测试用例。从证明角度看你不需要真的证明为什么箭一定要射在某个气球的右端点上只需要理解一个核心逻辑第一个气球的右端点是所有右端点中最靠左的位置而任何一支能引爆第一个气球的箭都必须落在小于等于这个右端点的位置。为了让这支箭尽可能覆盖更多后续气球把它移动到第一个气球的右端点是最优的——移动后它能覆盖的气球集合不会变小反而可能变大因为右端点是所有可行位置里最靠右的一个会覆盖到更多左端点靠左的气球。4.3 划分字母区间763合并区间的变体763 题要求把字符串划分成尽可能多的片段同一字母只能出现在一个片段里。每个字母都要有一段完整的“生存域”所以你需要先知道每个字母最后出现的位置把问题变成一系列区间合并从头扫描字符串维护当前片段中所有字母的 last 值最大值当遍历位置等于这个最大值时就说明当前片段可以切断了。def partitionLabels(self, s: str) - List[int]: last {c: i for i, c in enumerate(s)} res [] start end 0 for i, c in enumerate(s): end max(end, last[c]) if i end: res.append(end - start 1) start end 1 return res你可以把这道题理解为“不重叠区间的贪心版”只不过区间不是一个一个显式给出而是从字符最后出现位置推导出来的。一个典型的错误是一上来就把每个字符的出现区间列出来然后套用 435 的解法。其实没必要因为本题要的是尽量多划分而字母区间之间天然没有重叠冲突你只需要保证“所有包含同一字母的区间不被切开”用一个滑动窗口边界加一即可。我觉得这道题的训练价值在于它提醒你很多区间类贪心题并不一定直接给区间数据可能需要你先做一次哈希表映射才能把问题抽象成区间。如果你在做题时发现一道题很像区间调度但数据表现是字符串或数组优先考虑“映射到区间”这一步。5. 两道味道独特的 Hot 100 贪心题分发糖果与加油站5.1 分发糖果135左右两次遍历的约束拆解135 题要求你给每个孩子发糖果满足两个条件每个孩子至少一颗相邻孩子中评分高的孩子必须比评分低的孩子拿得更多。想一次性同时满足左高、右高两个方向其实很绕正确的做法是把约束拆开用两次单向遍历分别处理。第一遍从左到右保证每个孩子如果比左边评分高糖果数就比左边多一颗。第二遍从右到左保证每个孩子如果比右边评分高糖果数就至少比右边多一颗。两次结果取最大值即可。def candy(self, ratings: List[int]) - int: 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[i 1]: candies[i] max(candies[i], candies[i 1] 1) return sum(candies)这道题容易被误判成“每次取局部最大值然后周围递减”之类的复杂模拟但其实核心认知是一个孩子最后拿到的糖应该同时满足“来自左侧约束的糖数”和“来自右侧约束的糖数”的较大者。正因为两次遍历分别只满足一个方向的约束它们各自都是贪心的从左往右时每一步只需要看左边这是局部最优从右往左时每一步只需要看右边同样是局部最优。最后取最大值合并两个约束并不会破坏任何一边的满足条件因为取最大值只会让糖果数增加不会违反“评分更高就拿更多”的原则。5.2 加油站134总和与累加的符号判断134 题是环形的你从某个加油站出发可以带无上限的油每到一个加油站会加油然后消耗固定的油量去下一站问能不能绕一圈并给出起点编号。先判断整体可行性把所有 gas[i] - cost[i] 加起来如果总和为负说明“总入账小于总消耗”无论如何都走不完全程。这一步实际上是整个贪心策略的“全局约束”。在总和不为负的前提下真正的贪心选择就藏在累加过程中维护一个当前油量 cur如果 cur 在到达某站时变成负数说明从当前起点 start 到这一站的任何一点都不可能作为有效起点。def canCompleteCircuit(self, gas: List[int], cost: List[int]) - int: total, cur, start 0, 0, 0 for i in range(len(gas)): total gas[i] - cost[i] cur gas[i] - cost[i] if cur 0: start i 1 cur 0 return start if total 0 else -1为什么 cur 为负时直接重置起点是安全的假设从 start 出发到站 i 时油量变负那么对任意介于 start 和 i 之间的站点 k从 k 出发到 i 时油量只会小于从 start 出发到 i 时的油量。因为从 start 到 k 这段路程中start 持有的初始油量是正贡献若你从 k 出发就白白丢掉了 start 到 k 这段积累的净油。因此中间所有站点都不可能作为可行起点直接跳到 i1 不会漏掉正确解。比较有意思的是这道题的“贪”甚至不需要证明“选局部剩余最大”之类的策略它仅仅是在证明“失败的路径可以整体排除”。这种排除式贪心在算法面试里很常见像“摩尔投票法”里的抵消操作也是同一类思维建议你把它们放在一起体会。6. 贪心正确性的证明套路与实战判定标准6.1 举反例是最快的排除手段面试时很多人怕答错一上来就闷头写代码。我给的建议是先在脑子里尝试举一个反例推翻自己的想法。每个贪心策略都可以被挑战“如果每次选当前最优有没有可能当前最优把未来最优的路堵死了”如果短时间内举不出反例而且你能隐约感觉到这个策略不会让后续选择空间变小那么它极有可能就是正确解法。我经常举反例来检验排序类贪心。比如 435 题如果有人提出“按区间长度从小到大排序贪心地选最短的区间”立刻可以用反例杀掉它区间 [1, 10]、[2, 3]、[3, 4]最短的两个区间是 [3,4] 和 [2,3]但它们互相重叠如果先选 [2,3]就选不了 [3,4]最终只能保留 2 个区间。但按右端点排序可以保留 [2,3] 和 [3,4]留下 [1,10] 被删除。一个反例就能说明问题比长篇大论更高效。6.2 三种常见证明方法交换论证、贪心选择性质、最优子结构在需要真正证明的时候我常用的有三种方式。第一种是交换论证Exchange Argument适合绝大多数“排序后贪心”的问题。思路是假设存在一个最优解 S它和贪心解 G 在前若干步的选择不一致然后通过交换 S 中某个选择为 G 的选择证明 S 不会变差最终可以把 S 变换成 G从而说明 G 不劣于任何最优解。452 题的证明就是这样第一支箭如果不在最左气球的右端点上把它右移到右端点覆盖的气球集合不会缩小。第二种是结合贪心选择性质与最优子结构进行归纳证明。贪心选择性质说的是“存在一个最优解其中第一步就包含贪心做出的选择”最优子结构则是“第一步完成后剩余子问题的最优解可以独立求解”。两者同时成立就可以归纳证明整个贪心策略正确。55 题就是一个典型最远可达距离是明显的贪心选择你选了它之后剩下的问题又是“从可到达的区域继续延伸最远距离”的子问题。第三种是数学归纳与反证结合的方式通常用来证明这类问题“如果某一步贪心选择错误那么任何最优解都可以被调整成贪心解且结果更好或相同。”我在面试中一般不会把完整证明念一遍因为时间不够最关键的是把交换论证的核心讲清楚再补一句“哪一个局部性质保证后续不受影响”面试官基本就会认可。6.3 Hot 100 里哪些题“看着像贪心”但其实是别的类别我踩过一个比较深的坑把“暴力模拟”和“贪心”搞混。比如合并区间56 题你虽然要排序但核心只是线性扫描合并每一步没有真正意义上的“最优选择”它更像模拟。而根据身高重建队列406 题排序后的插入过程也偏向模拟你可以说它有贪心味道但严格来说不要求证明最优选择。同样的Hot 100 里有些题像 70 爬楼梯、198 打家劫舍第一眼可能会想到“每次走两步最优”或“隔着偷最优”但实际上它们更稳妥的做法是动态规划因为局部最优组合不出全局最优。我的判断标准是如果贪心策略要求“每步只保留一个状态”但问题有明显的“选择分支影响后续”那就该用 DP。贪心是“我替所有未来选择做决定”DP 是“我把所有选择都试探一遍”。面试时如果你发现自己的贪心代码需要记录多个候选值那很可能是贪心不成立需要回头考虑 DP。7. 建议的刷题顺序与个人经验7.1 建议刷题顺序Hot 100 里的贪心题不必按题号刷按模型分类会更有效。我自己的顺序是先用 121 和 122 建立“局部最优叠加全局最优”的直觉再做 55 和 45 感受“覆盖边界推进”的贪心代码风格然后集中刷 435、452、763 这三个区间题因为它们之间只有微妙差别非常适合对比记忆。最后用 134 和 135 收尾这两道题对贪心正确性的理解要求更高做完之后你再看其他贪心题会轻松很多。如果你还想额外加练可以在平台里搜“贪心”标签挑几道中等难度但不在 Hot 100 的题比如会议室相关、分发饼干、最长递增子序列的非 DP 解法等进一步巩固交换论证的感觉。刷题时我强烈建议你给每道题写一句“贪心选择是什么”比如“55 题贪心选择是维护最远可达位置”“452 题贪心选择是把箭射在当前最左气球的右端点”这样复习时一眼就能回忆起来。7.2 面试中遇到贪心题的解题节奏面试遇到贪心题我建议按这个节奏走。先确认题目能不能排序不能排序的话观察有没有可维护的极值变量然后快速枚举几种可能的贪心策略并尝试举反例排除不安全的策略接着和面试官简短交流你选择的贪心策略用一两句话解释“为什么局部最优不会破坏全局”最后再写代码。很多候选人一上来就写代码写完才发现策略不对反而拉胯。先说“我打算按右端点排序每次都保留结束最早的区间因为这样能给后面留最大空间”面试官会给你正面反馈。写代码时我还有一个习惯先把边界情况想清楚。区间题的空数组、单元素数组跳跃题的长度为 1股票题的降序数组都是最容易掉分的地方。Hot 100 里的贪心题虽然代码短但测试用例非常毒宁可多写两个断言也别贪快。另外如果题目给出的数据范围很大贪心往往是面试官期待的方向因为 O(n) 或 O(n log n) 是最优的如果你发现自己写出了 O(n²) 的解法大概率不是这道题的正解。最后再说一点个人体会我刷完 Hot 100 里的贪心题之后最大的感受是贪心算法不是数学竞赛里的某种高深结构它本质上是在说“这个问题的结构足够好好到不需要后悔”。很多初学者觉得贪心靠直觉、看天赋其实不是它靠的是你见过足够多的模型并且能在几秒内判断“这个局部信息能不能代表所有候选”。建议你把这几道题反复刷三遍每遍都先独立复现贪心策略再对照证明。刷熟之后你会发现Hot 100 之外的大多数贪心题几乎都是这几类模型的排列组合。