写在前面我刷 LeetCode Hot 100 的时候贪心算法是我觉得“代码最短、证明最难”的一类题。明明几行代码就能过但每次裁边界条件都要想半天。这篇是 Hot 100 刷题笔记的第 14 篇我把刷题过程中真正有用的贪心题套路、判断方法、常踩的坑和排查技巧一次性整理出来。内容不追求把所有题都贴一遍而是把最核心的题吃透尤其是 55、45、121 这三道几乎就是贪心章节的骨架你会感觉到它们的思路是相通的。1. 贪心算法到底是什么怎么判断一道题能吃这口饭1.1 贪心的核心局部最优能不能推出全局最优贪心算法不是一种具体的“算法模板”而是一整套决策策略每一步都在当前状态下做出一个看起来最优的选择并且不回头、不反悔假定这种“局部最优”累积起来就能得到“全局最优”。用生活类比来说就像你在一个陌生的楼梯间里找人每到一个平台就选择“看起来离目标更近”的那个楼梯口走出去。这个策略在有些楼层里能最快到达但如果你碰上的是那种绕来绕去的商场楼梯第一次选错可能就得走到死胡同再折返这时候贪心就失效了。所以判断一道题能不能用贪心本质上就是判断两件事当前的最优选择是否可以“锁定”不会被后续选择推翻全局最优能不能由若干局部最优拼接出来。如果这两条都成立贪心往往就是最优雅的思路。难点在于很多题目第一眼看起来“贪一下就行”实际却是不成立的。比如经典的找零钱问题用 25、10、5、1 分硬币时贪心是对的但如果换成 1、3、4 分的硬币要凑 6 分贪心会先选 4 分再选两个 1 分得到 3 枚硬币而正确答案是 33 只需要 2 枚。这就是典型的“伪贪心”。LeetCode 上刷贪心题首先要训练的其实是“识别哪些题真能贪”而不是一上来就写代码。在我个人经验里一个特别实用的“快速判断法”是思考在决策的某一刻是否有一个参数能被“只顾眼前”地优化而不影响之后的任何可能性。如果答案是否定的就应该往动态规划、回溯那个方向想。Hot 100 里的贪心题大多把这个参数设计得非常明显只是很多解法没跟你讲透。1.2 贪心与最优子结构动态规划的同胞兄弟简单说最优子结构就是“大问题的最优解里天然包含子问题的最优解”。举一个最容易被误会的例子爬楼梯问题你每次可以走 1 阶或 2 阶问到第 n 阶有多少种走法。这实际上是 斐波那契数列它显然不是贪心因为每一步的选择都不确定、需要记录多种状态。但到了跳跃游戏里问题变成了“最多能跳到哪”当我们站在某个位置时唯一需要关心的就是从这个位置最远能覆盖到哪。后续的每一个位置是否能到达只取决于之前所有位置的可达范围有没有覆盖到它。这也可以看作是某种“最优子结构”在起作用全局的“最大覆盖范围”是局部最大覆盖范围不断地往后传递。所以动态规划和贪心的关系有时候像双胞胎。区别在于动态规划会把所有可能的子问题结果都记下来最后避免重复计算贪心则只保留一个“最优候选”把它一路滚下去。理解这一点之后你就不太容易搞混了。Hot 100 里的“买卖股票的最佳时机”和“跳跃游戏”看起来完全不相关但当你把它们都放在“贪心”章节里看会发现维护的变量本质都是“到目前为止的最优值”再在遍历中不断比较更新。2. Hot 100 里最值得吃的 5 道贪心题2.1 55 跳跃游戏维护最远可达距离题目很直白给你一个非负整数数组 nums你初始位置在下标 0每个元素代表你在该位置可以跳跃的最大长度判断你是否能够到达最后一个下标。我第一次做这题的时候第一反应是 DFS 暴搜把所有跳跃路径都走一遍看看有没有能到达终点的。但一旦数组长度上了 10^4这种思路直接超时。正确做法是维护一个变量 maxReach表示当前能到达的最远下标然后从左到右遍历每个可达位置不断更新 maxReach max(maxReach, i nums[i])。如果某个时刻 i 已经大于 maxReach说明这个位置根本走不到直接返回 False。遍历结束后只要 maxReach 能覆盖到 n-1就说明可以到达。这道题之所以是贪心是因为在每个位置上我们不需要记录“有哪些路径能走到这”只需要记录“当前所有路径里能延伸到的最远边界是哪”。边界内部的位置天然都是可达的因为跳跃是连续的、范围是一段区间。这种“能维护一个区间边界并且边界单调扩展”的题目是典型的贪心形态。我当时总结了一个口诀看到“能否到达”“最小步数”“最远能到哪里”优先想能不能维护一个边界。2.2 45 跳跃游戏 II最少跳几次别被直觉带偏这道题是 55 的加强版问的是你一定能到达最后一个下标但最少需要跳几次。很多人第一反应是“每次跳到能跳最远的位置就行”。这个直觉对不对我拿一个反例给你看nums [2, 3, 1, 1, 4]站在下标 0能跳 1 步到下标 1也能跳 2 步到下标 2。按“最远”的贪心你会跳到下标 2因为 022但到了下标 2 只能再跳 1 步到下标 3下标 3 再跳 1 步到下标 4总步数是 3。而正确答案只需要 2 步先跳 1 步到下标 1再跳 3 步直接到终点。所以正确的贪心并不是“每次选跳得最远的位置”而是“在当前这一跳能够覆盖的范围内选择能让你下一步覆盖范围更远的那个位置”。这和 BFS 的思想一致把“一跳”看作一层每走完一层就扩展出一个新的覆盖区间步数加一。实现上需要两个变量currentEnd 表示当前这一跳的最远边界farthest 表示在当前边界内所有位置能延伸出去的最远距离。当遍历到 currentEnd 时说明这一跳已经走满跳跃次数加一然后把 currentEnd 更新为 farthest。这道题的代码甚至比 55 还短但如果没有理解“区间扩展”这个层次纯靠背代码很容易出错。我在后面“核心代码实现”一节里会给出完整代码和每一行的边界说明可以对照着看。2.3 121 买卖股票的最佳时机只找历史最低点121 题表面上是股票问题实际上可以说是贪心里“维护最优变量”的启蒙题给定一个数组 pricesprices[i] 表示第 i 天的股票价格你只能选择某一天买入并在之后的某一天卖出求最大利润。如果不能获利返回 0。如果不懂套路新手会写两层循环枚举所有买入卖出组合O(n^2) 在数据量大了之后直接超时。贪心解法非常简洁遍历价格时维护两个变量minPrice 表示到今天为止出现过的最低价格maxProfit 表示到今天为止能获得的最大利润。每遇到一天先算一下“如果我在之前的最低点买入在这一天卖出能赚多少”然后更新最大利润同时把当天价格和 minPrice 比较更新最低点。为什么说这是贪心因为在每个日期你只需要维护“历史最优买入时机”这一个信息而不是记录每一天作为买入点的完整利润表。每一天的决策要不要用今天作为卖出点是独立的不会影响未来。买点被锁定为“当前见过的最低价格”这个选择局部最优而全局最大利润必然来自某个最低点所以它整体也是最优的。我偏好把“股票问题”和“跳跃游戏”放在一起看前者维护的是“已知最小值 最大差值”后者维护的是“已知最远覆盖边界”。本质上都是在遍历过程中不断用新信息刷新一个全局候选值。贪心题刷多了以后你会越来越有这种感觉很多题的代码结构长得像同一个模板。2.4 763 划分字母区间哈希表定边界贪心扩区间这道题给你一个字符串 s要求把它划分成尽可能多的片段使得同一个字母只出现在其中一个片段中返回每个片段的长度。例如 s ababcbacadefegdehijhklij结果是 [9, 7, 8]。思路分两步第一遍扫描用哈希表记录每个字母最后出现的位置第二遍扫描维护当前片段的 start 和 end。每遇到一个字符就用“该字符最后出现的位置”去更新 end max(end, last[c])当遍历到的下标 i 等于 end 时说明这个片段已经闭合记录长度 end - start 1并重置 start end 1。这个逻辑本质上就是“区间覆盖”每个字符的最后出现位置决定了它所属片段的最小右边界要覆盖所有字符就必须把右边界扩展到这些最大值。它是个贪心因为在扫描过程中我们永远只扩大当前片段的范围直到不可能再缩回去。相比前两道题这道题更直观但很能训练“两趟扫描 贪心扩展”的思路在面试里出现频率也不低。2.5 134 加油站累计油量才是真相加油站问题是 Hot 100 里容易被忽略的一道贪心题。题目给了两个数组 gas 和 costgas[i] 表示第 i 个加油站能加的油量cost[i] 表示从第 i 个加油站开到下一个加油站需要消耗的油量。假设油箱容量无限问从哪个加油站出发可以绕环路一圈如果不存在则返回 -1。这道题的贪心很反直觉我们不去模拟每一段路能不能走通而是维护两个累计变量total 和 curr。total 记录整个环形路线上的总油量减去总消耗如果 total 0说明无论从哪出发都不可能走完直接返回 -1。curr 记录从当前起点开始的累计剩余油量如果某一段路程中 curr 变成负数说明起点不可能在当前位置之前直接把起点设为 i1并重置 curr 为 0。为什么这个策略是对的因为如果从 start 出发到 i 时油不够了那么从 start 到 i 之间的任何一个加油站重新出发都会在同样的位置没油。因为到达这些站的时候你手上至少有从 start 带过来的“净剩油”如果带着净剩油都到不了 i1那换成从中间某站出发油量只会更少更不可能到。这就是典型的最优子结构。这道题的代码非常短但推导过程特别值得写下来面试时如果你能把“为什么”讲清楚会非常加分。3. 完整代码实现与避坑细节3.1 五道题的 Python 代码速查直接上代码都是我实测能通过 LeetCode 的版本注释标在关键行。# 55. 跳跃游戏 def canJump(nums): max_reach 0 n len(nums) for i in range(n): if i max_reach: return False max_reach max(max_reach, i nums[i]) if max_reach n - 1: return True return True# 45. 跳跃游戏 II def jump(nums): n len(nums) if n 1: return 0 jumps 0 current_end 0 farthest 0 for i in range(n): farthest max(farthest, i nums[i]) if i current_end: jumps 1 current_end farthest if current_end n - 1: break return jumps# 121. 买卖股票的最佳时机 def maxProfit(prices): min_price float(inf) max_profit 0 for price in prices: if price min_price: min_price price elif price - min_price max_profit: max_profit price - min_price return max_profit# 763. 划分字母区间 def partitionLabels(s): last {c: i for i, c in enumerate(s)} ans [] start end 0 for i, c in enumerate(s): end max(end, last[c]) if i end: ans.append(end - start 1) start end 1 return ans# 134. 加油站 def canCompleteCircuit(gas, cost): total 0 curr 0 start 0 for i in range(len(gas)): total gas[i] - cost[i] curr gas[i] - cost[i] if curr 0: start i 1 curr 0 return start if total 0 else -1这几段代码都很短但每一行都有讲究。尤其要注意 45 题的循环终止条件什么时候 break什么时候不 break写错了很容易陷入死循环或者多算一次跳跃。我的经验是先把 current_end 和 farthest 两个变量的含义在纸上画出来再对着代码走一个简单例子基本就不会错。3.2 边界条件与复杂度分析贪心题代码短边界条件反而容易翻车。我在刷题时整理了一份高频边界条件清单写代码前会先想一遍题目边界测试用例预期输出容易错的地方55. 跳跃游戏nums [0]True初始位置就是最后一位别在循环外提前返回 False55. 跳跃游戏nums [0, 2, 3]False第一个位置跳不出去循环到 i1 时 i max_reach45. 跳跃游戏 IInums [0]0长度为 1 时不需要跳跃45. 跳跃游戏 IInums [1, 2]1current_end 在 i0 时就更新注意 break 条件121. 买卖股票prices [1]0价格持续下跌时最大利润永远是 0763. 划分字母区间s abc[1, 1, 1]每个字母都只出现一次时每个字符都是独立片段134. 加油站gas [2], cost [3]-1total 0 时直接返回 -1不要继续算 start复杂度方面55 题、45 题、121 题、134 题都是 O(n) 时间、O(1) 空间763 题因为要记录每个字母的最后位置是 O(n) 时间、O(字符集大小) 空间。这个复杂度在 LeetCode 的题目约束下都是最优的面试时如果被问“能不能优化”基本可以直接说没有更好理论复杂度。还有一个实战小技巧这些题里出现的大多是数组、字符串用 Python 写起来天然有优势但要注意别在循环里频繁调用 len() 或数组切片否则 O(n) 会被常数拖慢。切片在 Python 里是创建新数组复杂度 O(k)贪心题里如果切了表面看是 O(n)实际可能变成 O(n^2)在极端数据下很容易超时。4. 贪心 vs 动态规划差之毫厘失之千里4.1 怎么快速区分一道题应该用贪心还是 DP面试被问“为什么这题用贪心不用动态规划”是非常高频的追问。我通常分三步想第一步看当前决策是否影响之后的状态。如果你选择了“今天买入股票”这个决定会不会导致明天无法卖出股票问题不会因为“买入”只是记录一个最低价并不消耗任何资源但如果你在“0/1 背包”里选了某个东西背包容量变小就会影响之后能不能选其他东西所以背包问题不能简单贪心。第二步看局部最优是否有可能被推翻。在跳跃游戏 II 里如果把“每次跳得最远”作为贪心策略它会被后面的位置推翻因为跳得最远不一定让下一步覆盖更远。正确的贪心是“在当前覆盖范围内找到能扩展最远的那个落脚点”这个选择是不会被推翻的所以它才能成立。第三步实在判断不了就先写暴力/回溯然后看数据范围。如果 n 很小比如小于 15回溯也能过如果 n 到 10^5 以上大概率是贪心或 DP。这时再用一个特例去验证贪心是否成立。这个方法听起来土但很实用。我在刷题时见过不少人把“爬楼梯”和“跳跃游戏”搞混。爬楼梯问的是“方案数”每一步的走法组合会产生很多可能性所以必须用 DP 或滚动数组跳跃游戏问的是“能不能到终点”只关心覆盖面所以贪心就够了。核心差异就在于你需要记录“所有可能”还是只关心“最优/最远”。4.2 经典的“伪贪心”陷阱看看你有没有踩过除了找零钱问题LeetCode 里还有一些看起来很像贪心、实际不能贪的题目比如“无重叠区间”和“合并区间”。很多初学者看到“区间”就直接想排序后拿贪心套但这两题的内核其实不一样无重叠区间435要求移除最少数量的区间使剩余区间互不重叠。这道题确实是贪心但关键在于按区间右端点排序而不是左端点。按右端点排序后每次选结束最早的区间就能给后面的区间留出最多的空间。如果不理解这一点按左端点排序后贪心会得出错误结果。合并区间56也是对区间排序但它其实更像模拟不是贪心。排序后逐个比较当前区间和已合并区间的右端点能合并就合并不能合并就开新区间。以我自己的经验区分这类题最有效的办法是问自己排序之后我是在维护一个“最优答案”吗如果是再想“这个最优答案会不会在后续更新时被推翻”。在无重叠区间中按右端点排序后被选中的区间永远不会被后续区间推翻所以它是真正的贪心而合并区间只是把相邻区间播在一起没有“决策”过程更像是双指针/模拟。顺便提醒一句写区间题之前先把排序规则想清楚。Python 里可以用 keylambda x: x[1] 按区间右端点升序排序。这个排序规则虽然只是一行代码但在面试里经常会被追问“为什么这样排序不那样排序”你如果能讲清楚背后的空间交换逻辑面试官印象分会有明显提升。4.3 贪心算法的严谨性能不能不用反例说话很多人刷贪心题时会觉得“反正 AC 了就对”。但 LeetCode 的测试用例再多也未必覆盖所有边界。想真正掌握贪心你得学会给自己“找反例”。一个容易上手的训练方法是拿到一道题后先写一个直觉上的贪心方案然后用 3 到 5 个极端例子去攻击它。比如跳跃游戏 II刚开始直觉“每次跳最远”我拿 [2, 3, 1, 1, 4] 一测就发现不对。再比如换零钱换成 [1, 3, 4]凑 6 分贪心得到 3 枚最优是 2 枚也是立刻就被反例推翻。这套“先假设再攻击”的流程本质上就是数学证明里的反证法。我练习的时候会在草稿纸上写清楚“如果贪心策略是 S那么是否存在某个局部最优选择 L使得选定 L 后后续无论如何都无法达到全局最优”。如果找得到这题就大概率不是贪心。这个过程一开始很慢但练十几道题之后速度会快很多面试时面对“这题能贪吗”这种问题你也能更笃定地给出答案。5. 刷题中我踩过的坑和排查技巧实录5.1 写错边界条件排错一小时的亲身经历有一道 45 题我第一次提交时一直报错最终发现是 break 时机的问题。我当时的代码在 current_end 更新后没有检查是否已经覆盖到最后下标导致循环继续执行jumps 被多加了一次。后来我总结出的排查步骤是这样的先用最朴素的用例走一遍比如 nums [1, 2]把 i、current_end、farthest、jumps 每一步都写在纸上打印这三个变量的变化过程和纸上推导对比如果发现跳数多 1优先怀疑循环结束时机而不是整体思路。我在代码里临时加打印输出结果类似这样i0, farthest1, current_end0 - jumps1, current_end1 i1, farthest3, current_end1 - jumps2, current_end3当 current_end3 已经大于等于 n-11 时理论上应该直接返回。如果没 break就会继续循环到 i2再次触发 i current_endjumps 变成 3。这就是为什么代码里要在更新 current_end 后立刻判断是否已经覆盖终点。这种细节不实际调试很难发现所以我强烈建议刷题时用 print 调试别怕麻烦。另一个常见坑在 763 题。刚开始我以为只需要记录每个字母第一次出现的位置结果发现划分的区间边界算不对。因为一个片段要覆盖某个字母的所有出现位置必须用最后一次出现的位置来扩展右边界。我第一次用 start 和 end 两个变量时在 i end 的判断里没有重置 start导致第二段长度算错。这种错误通过加一条打印语句就能看出来但如果你连“为什么要记录最后出现位置”都不理解就很容易写出逻辑上“感觉对”但实际错得一塌糊涂的版本。5.2 我的排错套路从暴力解出发这是我最想分享的一个经验如果一道贪心题你绞尽脑汁也想不出解法先写一个暴力解哪怕是 O(n^2) 或者 O(2^n) 的都行。写暴力解的过程中你会自然而然地把题目中的状态变化梳理清楚。然后你再从暴力解里找重复计算思考哪些信息是可以被“压缩”成单个最优变量的。这个方法帮我在面试里解决过好几道没见过的题。举个例子55 题如果写暴力就是从每个位置 DFS 搜索所有可跳距离你会发现大量状态是重复的因为只要 maxReach 能覆盖到某个位置就不用再关心它是通过哪条路径到达的。把这个“压缩”过程想明白贪心解法就是水到渠成的事。相比之下如果你一上来就背贪心解法遇到变形题还是会卡壳。个人还有一个习惯LeetCode 刷题时每道贪心题我都会在题解区找一个已经 AC 的代码用自己构造的测试用例跑一遍再对比一下我和它的边界处理差异。这样能学到很多题解里不会明说的细节比如 45 题要不要处理 n 1 的情况、134 题里 total 和 curr 的累计顺序能不能交换这些细节光靠看代码是看不出来的必须自己动手试。5.3 刷题时间分配与 Hot 100 贪心章节的刷法建议Hot 100 贪心题不算多但每道题都很典型。我建议按这个顺序刷先刷 121买卖股票入门理解“维护一个最优变量”再刷 55 和 45掌握“区间覆盖边界”的贪心形态然后用 763 练哈希表辅助贪心最后用 134 体会“累计量”这种隐藏贪心条件。每道题刷完别急着下一题花 3 分钟在草稿纸上写一下“这题我在哪个环节做了局部最优决策”。如果写不出来说明你还没真正理解这道题的贪心本质。把这个习惯坚持下去你会发现自己判断“能不能贪”的速度明显变快。从时间效率来说Hot 100 整套刷下来也不需要每天刷很多题。我的节奏是每天 2 到 3 道新题加 1 道前一天的重做贪心章节大概用了 5 天。重点不是题量而是每道题都能独立推导出解法哪怕慢一点也没关系。你刷到后面会发现很多所谓“新题”不过是这几种贪心形态的变体而已。6. 对贪心章节的一些个人体会我在刷完 Hot 100 的贪心部分之后最大的感受是贪心算法的代码往往很简短但它的思维门槛一点也不低。一道题的贪心解法写出来可能不到 10 行可为什么这样写、为什么这个变量能在遍历中不断更新才是面试真正想考察的东西。想通这一点之后我再也不背题解代码了而是先把题目当成一道“证明题”来做。如果要说一点对后来者最实用的建议那就是刷贪心题时请在你的草稿纸上充分练习“举反例”这个动作。无论是自己把题做错了还是看别人题解时“觉得有道理”都去试试能不能找到一个反例推翻眼前这个解法。这个习惯不一定能让你立刻 AC 所有题但会让你脱离“背模板”的状态真正开始像工程师一样思考问题。