如果你刷 LeetCode Hot 100 刷到中段，碰到“贪心算法”这个标签，大概率会经历一个过程：第一眼看题觉得“这有什么难的，不就是每次选最优吗”，自己写一版交上去之后 WA 得莫名其妙，再去看题解又觉得“啊原来这么简单”，但下一道题还是不会。贪心算法就是这样一种题型：它看起来是“常识”，实际上考的是你能不能严格证明“局部最优能推出全局最优”这件事。这篇内容我会结合自己刷 Hot 100 的经验，把这几年高频出现的贪心题拆开揉碎讲清楚，包括核心判断标准、经典题型套路、容易和贪心混淆的题（比如热词里常见的目标和、爱吃香蕉的狒狒、最长回文子串），以及一套能直接落地的刷题顺序和笔记方法。适合正在集中刷 Hot 100、准备面试、或者想搞明白“到底什么时候能用贪心”的读者。
1. 贪心算法到底在 Hot 100 里考什么
1.1 热词里那些“看似贪心”的题
先说一个有意思的现象。你在搜索“leetcode hot100 贪心算法”的时候，结果里经常混进来几道其实并不是贪心的题，比如“目标和”（LeetCode 494）、“爱吃香蕉的狒狒”（LeetCode 875）、“最长回文子串”（LeetCode 5）。它们为什么会被搜到一起？因为这些题有个共同点：题目描述里天然带着“选择”“最优”“速度”这类词，让人直觉上觉得应该用贪心。
我自己也踩过这个坑。拿 494 目标和来说，题目给你一个数组和一个 target，要求你在每个数前面放正号或负号，问最后表达式结果等于 target 的方案数。我一开始想的是“每一步尽量接近 target，不就能凑出方案吗”，实际写出来立刻发现漏解。因为这道题要的是“方案数”，不是“能否达到”，你每步做的符号选择会直接影响后续所有组合，一旦只保留一个“看起来最接近”的状态，其他合法路径全被丢掉了。这种情况本质上是带后效性的，贪心根本处理不了，正确做法是 DFS 记忆化或者 DP。
再比如 875 爱吃香蕉的狒狒。题目说有一堆香蕉，每小时只能选择一堆吃，最多吃 k 根，如果一堆不够 k 根就吃完但要花完整的一小时，让你求能在 h 小时内吃完的最小速度 k。这题我见过不少人上来就说“贪心，每小时吃最多的那堆”，但真的不对。你要找的是一个速度阈值，而速度越大、耗时越少，这是一个典型的单调关系，所以标准解法是二分答案，每次用 mid 速度模拟一下总耗时，而不是贪心选堆。
还有 5 最长回文子串，它本质是中心扩展或区间 DP，也不是贪心。但这三道题频繁和“贪心算法”一起出现在搜索热词里，说明大家刷题时的真实困惑是：我没办法快速判断一道题到底该不该贪心。所以这一节我们先建立判断标准。
1.2 贪心的本质：局部最优为什么能推出全局最优
贪心算法的定义很简单：每一步都选择当前看起来最优的决策，并且做出决策后不再回退。但“当前最优”要想成为“全局最优”，需要满足两个条件：
- 贪心选择性质：存在一个整体最优解，是从局部最优选择开始构造出来的。
- 最优子结构：问题的最优解包含子问题的最优解。
网上喜欢用找零钱来举例，实际上这个例子有点坑，因为用 [1, 3, 4] 找零 6 时，贪心会得到 4+1+1 = 3 枚，但最优解是 3+3 = 2 枚，秒变反例。所以别拿找零当贪心的万能例子。真正适合生活化理解的场景是“活动安排”：你有若干会议要参加，每个会议有开始和结束时间，问最多能参加多少个。策略是“每次选结束时间最早的会议”，因为结束早能给后面留更多空间，这个决策一旦做出就不用改，而且不会影响后续会议的选择。这就是贪心。
我刷 Hot 100 的一个体会是：贪心题并不是靠“猜”做的，它更像在写一场小型证明。你提出一个贪心策略后，要能用交换论证或反证法说明为什么它不差于任何最优解。面试时考官问“为什么贪心是对的”，很多时候不是想听你背概念，而是想确认你有没有能力用“如果最优解第一次选择和贪心选择不同，我可以通过交换把它们变成一样，且不使结果变差”这套逻辑自圆其说。
这套思维虽然抽象，但应付 Hot 100 里的贪心题完全够用，因为高频题就那几个变体：排序后逐个决策、一次遍历维护边界、区间排序后合并或计数。接下来我就按类型拆解。
2. 高频贪心题拆解：从 Hot 100 里挑出的代表题
2.1 分发饼干（LeetCode 455）：排序双指针是贪心的入门骨架
如果你刚开始接触贪心，我建议从分发饼干入手。题目是给一组孩子胃口值 g 和一组饼干尺寸 s，每块饼干最多喂一个孩子，只有当饼干尺寸大于等于孩子胃口时才能满足，问你最多能满足几个孩子。
这题的贪心策略非常直觉：先把孩子胃口和饼干尺寸都从小到大排序，然后用小饼干去喂小胃口的孩子，避免浪费大饼干。实现就是双指针：
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复杂度是 O(n log n)，主要来自排序。这个题虽然简单，但它展示了贪心题最常见的第一步：预处理排序。排序让你可以用一种“有顺序”的方式去做局部决策，之后刷跳跃游戏、合并区间、气球题，你会发现排序无处不在。这个双指针里还有个细节：饼干指针 j 无论如何都要前进，因为当前这块饼干要么满足了当前孩子，要么喂不饱当前孩子，喂不饱的话它也不可能满足后面胃口更大的孩子，所以直接丢弃。
2.2 跳跃游戏 I / II（LeetCode 55 / 45）：一次遍历维护最远可达
跳跃游戏是 Hot 100 里最经典的贪心题之一，也是面试高频。第一问是：从数组第一个位置出发，nums[i] 表示你在下标 i 最多能往后跳多远，问能否跳到最后一个下标。
我的第一反应是“深搜每个位置所有的跳法”，但看数据范围就知道没必要。更聪明的做法是维护一个变量 reach，表示目前能到达的最远位置。从头遍历数组，只要当前下标 i 在 reach 范围内，就尝试用 i + nums[i] 更新 reach；一旦 reach 超过或等于 n-1，直接返回 True。
def canJump(nums): n = len(nums) reach = 0 for i in range(n): if i > reach: return False reach = max(reach, i + nums[i]) if reach >= n - 1: return True return True为什么是对的？因为每次“能跳得最远”都是当前步的局部最大值，而可达范围是连续扩展的：只要 i 没超过 reach，就说明存在一条路径到达 i，那么从 i 出发能到的地方当然也能合并进 reach。如果遍历到某个 i 已经大于 reach，说明中间断了，后面不可能到。这个推理本质上就是贪心选择性质，整个可达范围只增不减。
第二问跳跃游戏 II 升级成：保证能到达最后一个下标，求最少跳几次。核心思路还是维护“最远可达”，但多了一个“步数边界”的概念。我维护两个变量：当前这一步能覆盖的最远位置 cur_end，以及下一步能覆盖的最远位置 farthest。遍历 i 时持续更新 farthest，当 i 走到 cur_end 时，说明当前这一步已经到极限，必须跳一次，然后把 cur_end 更新为 farthest。
def jump(nums): n = len(nums) if n <= 1: return 0 jumps = 0 cur_end = 0 farthest = 0 for i in range(n - 1): farthest = max(farthest, i + nums[i]) if i == cur_end: jumps += 1 cur_end = farthest if cur_end >= n - 1: break return jumps这里有个特别容易写错的点：循环范围是 n-1，不是 n。因为只要更新完最后一个位置之前的步数就能到达末尾，如果遍历到最后一个元素才触发 jumps += 1，会多算一步。另外，第 45 题虽然标着贪心，但不少人喜欢用 BFS 或 DP 做，也能过，只是贪心写法复杂度 O(n) 而且代码最简单。
2.3 买卖股票的最佳时机 II（LeetCode 122）：把上涨段切碎
股票类问题在 Hot 100 里有好几道，最容易和贪心扯上关系的是第二题“买卖股票的最佳时机 II”：“你可以多次买卖一支股票，但手里最多持有一股，且卖出当天可以再买入，求最大利润。”
这个题我第一次做的时候想复杂了，以为要模拟买卖点。后来发现一个极其简单的贪心：只要第二天的价格比第一天高，就在前一天买入、后一天卖出，把每天的涨幅累加。也就是说，一段连续上涨的利润可以拆成每天的小利润。
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代码看起来简短到让人怀疑，但它确实是最优解，复杂度 O(n)。贪心成立的关键在于交易次数没有上限，所以每一次“正差值”都是可以独立兑现的利润，不会占用别的机会。这里需要对比一下 121 题“买卖股票的最佳时机”：那题只能交易一次，所以你不能这么写，得维护一个历史最低价格，同时更新“当前价格减历史最低价”的最大值，本质更接近动态规划中的状态维护。很多人把这两题混在一起背代码，背完就串台了。我建议你把它们放在一起刷，重点体会“为什么限制交易次数后，贪心就失效了”。
2.4 划分字母区间（LeetCode 763）：先统计最后出现位置
另一道很有代表性的 Hot 100 贪心题是划分字母区间。给你一个字符串，要求把字符串划分成尽可能多的片段，同一个字母只能出现在一个片段中，输出每个片段的长度。
策略也不复杂：先遍历一遍字符串，记录每个字符最后一次出现的位置；再遍历第二遍，维护一个 end，表示当前片段中所有字符最后出现位置的最大值。当遍历到的下标等于 end 时，说明当前片段可以安全切开了。
def partitionLabels(s): last = {} for i, ch in enumerate(s): last[ch] = i res = [] start = 0 end = 0 for i, ch in enumerate(s): end = max(end, last[ch]) if i == end: res.append(end - start + 1) start = i + 1 return res这题的贪心点在于：遍历时不断把 end 往外扩，本质是在保证“同一字母不跨区”这个硬约束下，尽量在最早可分割的位置切下去。一旦 i == end，立刻分割，不会继续往后拖，因为再拖只会让当前片段变大、总片段数变少，和“尽可能多片段”的目标矛盾。“遇到边界就切”这个决策不需要回退，所以是贪心。
一个容易被忽略的细节是 last 字典里存的是最后出现位置，而不是首字符次数。也有人在第二次遍历时用 set 统计已出现字符，可以但没必要，O(n) 空间和一次扫描已经是最优。
2.5 区间贪心：用最少数量的箭引爆气球（LeetCode 452）
区间贪心是 Hot 100 里比较能拉开差距的一类，代表题就是“用最少数量的箭引爆气球”。每个气球是一个闭区间 [x_start, x_end]，弓箭从某个 x 位置垂直射出，可以引爆所有包含这个 x 的气球，问你最少射几箭。
常规贪心策略是：先把所有区间按右端点从小到大排序，然后选择第一支箭的位置为第一个区间的右端点，之后遍历所有区间，如果当前区间的左端点小于等于这支箭的位置，说明它已经被引爆；否则就要新射一箭，并把新箭位置更新为这个区间的右端点。
def findMinArrowShots(points): if not points: return 0 points.sort(key=lambda x: x[1]) arrows = 1 cur_pos = points[0][1] for start, end in points[1:]: if start > cur_pos: arrows += 1 cur_pos = end return arrows为什么按右端点排序而不是左端点？因为右端点越早结束的区间，越应该优先“用箭覆盖”，这样箭的位置靠左，能给后面区间留更多重叠空间。如果用左端点排序，你的箭会偏向右侧，很容易漏掉一些结束早但起点也早的区间。这个细节你在做 435 无重叠区间时也会遇到，那题先按右端点排序然后贪心保留区间，思路一模一样。
2.6 其他值得做的 Hot 100 贪心题
Hot 100 里的贪心题远不止上面几道，我列一个自己的做题清单供你参考：
| 题目 | 核心思路 | 难点/易错点 |
|---|---|---|
| 121. 买卖股票的最佳时机 | 维护历史最低价，逐步更新最大利润 | 限制一次交易，不能把正差累加 |
| 134. 加油站 | 累计油量小于0时更换起点 | 证明为什么失败段开头都不可能是起点 |
| 135. 分发糖果 | 先左到右，再右到左两次遍历 | 第二次遍历也要保证从左到右的约束 |
| 435. 无重叠区间 | 按右端点排序，贪心保留结束早的区间 | 和 452 互为镜像，可一起刷 |
| 56. 合并区间 | 按左端点排序后扩张右边界 | 注意区间包含时不要重置右边界 |
| 53. 最大子数组和 | 局部和小于0就丢弃重开 | Kadane 思想，也可归为 DP |
你把这些题做完就会发现，贪心题的高频考点其实很少，排序 + 一次遍历 + 边界维护占了绝大多数。如果你能把 2.1 到 2.5 这五道题的思路讲清楚，再做这组补充题，基本就覆盖了面试中 80% 的贪心场景。
3. 贪心和动态规划到底怎么分：边界案例辨析
3.1 靠“下一步状态”决定要不要选择：目标和的教训
回到前面提到的“目标和”LeetCode 494。为什么这道题不能用贪心？因为它要的不是“是否能达到 target”，而是“有多少种不同的符号组合能让表达式等于 target”。贪心的每一步只保留一个最优状态，但对于计数题，你需要保留“每个可能和值对应的方案数”，于是自然就退化成 DP 了。
我用一个很短的例子说明：数组是 [1, 1, 1, 1, 1]，target 是 3，答案是 5。你发现“每次选离 target 更近的符号”这个规则根本没法定义，因为中途离 target 近不代表最终方案数多。这题的典型解法是 DFS 加记忆化，或者把问题看成“选出若干数取正号，其余取负号”，转换成子集和计数，再用背包 DP 解决。所以说，看到“方案数”“路径数”“组合数”这些词，第一反应应该是 DP 或 DFS，不是贪心。
3.2 最常见的判断方法
在实际刷题时，我给自己定了三条判断规则，能快速过滤掉大部分该用 DP 的题：
- 看要不要枚举中间状态：如果一个问题需要保留“多种可能的中间结果”才能得到最终答案，那它是 DP；如果直接从当前状态选一个走下去就行，再考虑贪心。
- 看选择有没有后效性：当前决策会不会影响后续所有决策的可行性？如果会，而且影响方式不止一种，贪心大概率错。跳跃游戏里“选择哪个位置跳”不会破坏可达范围的连续性，所以能贪心；目标和里“选正号还是负号”会改变后续所有状态，所以不行。
- 看问题的结果类型：求最大最小、最多个数、最少次数，且决策顺序性强的，可以优先想贪心；求方案总数、路径方案、可行性组合的，优先 DP。
“爱吃香蕉的狒狒”则属于第三类情况：它求的是“最小速度”，但 speed 和耗时之间是单调关系，本质上是在一个单调函数上找左边界，属于二分答案的套路。遇到“求最小可行值”的时候，先别急着贪，问问自己答案是否关于某个参数单调。如果是，果断二分。
3.3 容易搞混的题目对照表
我整理了一张自己在刷题时反复对照的表格，能帮你快速建立“这道题归哪类”的直觉：
| 题目 | 适用方法 | 关键判断依据 |
|---|---|---|
| 55. 跳跃游戏 | 贪心 | 只需维护可达范围，范围单调扩展 |
| 45. 跳跃游戏 II | 贪心 | 最少步数，边界到点就跳 |
| 70. 爬楼梯 | DP | 求方案数，需要累加子状态 |
| 494. 目标和 | DP | 求方案数，符号选择影响后续状态 |
| 322. 零钱兑换 | DP | 币值不满足贪心条件时，需要枚举组合 |
| 122. 买卖股票最佳时机 II | 贪心 | 不限交易次数，每个正差独立 |
| 121. 买卖股票最佳时机 | DP/维护状态 | 只能交易一次，需要记录持有/未持有 |
| 875. 爱吃香蕉的狒狒 | 二分答案 | 速度单调，最小可行值问题 |
这张表最想提醒你的是：即使是同一个场景，加一个限制条件后方法就会变。股票题就是最好的例子。所以刷题时不要只背“这道题用什么方法”，更要理解“限制条件改变了哪部分结构，导致方法切换”。
4. 刷题指南：Hot 100 贪心题的进阶路线
4.1 建议的练习顺序
如果你准备集中刷贪心，我不建议直接上跳跃游戏 II 或分发糖果这种需要一点推理的题，很容易心态崩。我个人的练习顺序是分三个梯队：
第一梯队：建立“排序 + 双指针”直觉。做 455 分发饼干、392 判断子序列、53 最大子数组和。这几道题代码短、逻辑直观，能让你快速体会到“贪心策略 + 一次遍历”大概长什么样。
第二梯队：理解“单变量维护边界”。做 121、122、55。这三题都在做同一件事：用一个变量记录历史最优或当前可达边界。做完你会觉得“很多贪心其实就是把问题压缩成一个可更新的量”。
第三梯队：区间和进阶。做 452、435、56、763，然后挑战 134、135、45。这些题需要你主动想“排序应该按哪个端点”“要不要跨区间更新”，思考密度明显更大，也是面试问“为什么贪心正确”的高发区。
这样分层的逻辑是：贪心题的难度不在于想出一个策略，而在于“敢不敢提交”。先刷简单题建立信心，再逐步接触需要证明和前后两次扫描的题，比一上来就啃硬骨头效果好很多。
4.2 怎么整理一份真正有用的贪心题解
刷到一定量之后你会发现，题解代码网上到处都是，真正缺的是“为什么这个策略是对的”的文字解释。我现在的记笔记模板是五段式：
- 一句话题意：不复制题目，用自己的话说清楚输入输出。
- 贪心策略：用一句“每次做什么”写清楚，例如“按右端点排序，每支箭射到当前区间右端点”。
- 为什么成立：写交换论证或反证法的关键步骤。哪怕只写一句话“交换任意两个选择顺序不改变可行性，所以按最早结束的来不会变差”也比不写好。
- 复杂度：时间、空间各一行。
- 踩坑记录：比如“45 题循环只能到 n-1”“452 题 start == cur_pos 时算重叠”。
为什么一定要写“为什么成立”？因为面试时这一块的分数占比很高。面试官让你做贪心题，通常不会满足于你说“我猜应该这样”，而会追问“如果我把这个策略换一下会怎样”。你笔记里写过一遍证明，面试时就能用自己的话说出来，而不是临时卡壳。
4.3 周赛和限时做题的实战策略
平时刷题和真实面试/周赛还有个区别：时间压力。我参加周赛 430 场次的时候有一个非常深的体会，很多题目不是“做不出”，而是“一开始方向错了，浪费大量时间”。为了降低翻车概率，我在五分钟内会按这个顺序快速判断：
先看问题问的是什么。如果问“最大/最小/最少次数”，并且题目里有明显的“顺序决策”或“排序后贪心”的味道，就先把贪心策略写出来，拿题目的示例手跑一遍。如果示例能过，再想几个极端小例子手动验证。比如零钱兑换这种题，我第一反应不是贪心，而是先想“任意币值下贪心一定对吗”，一旦想到 [1, 3, 4] target=6 这个反例，就立刻转 DP。反之，像跳跃游戏这种“可达范围扩张”，很难举出反例，就可以果断往下写。
如果问题里有“方案数”“路径数”“不同方法”这些词，我会直接跳过贪心，进入 DP 或 DFS。如果答案对某个参数有明确单调性，我会先写一个暴力验证函数，再套二分框架。这套判断流程能在周赛里省掉大量试错。
5. 常见误区与调试心得
5.1 不证明直接写，反例来了就懵
我刚开始刷贪心时最容易犯的错就是“觉得对就开写”。后来被自己一个反例教育了：零钱兑换，coins 是 [1, 3, 4]，amount 是 6。按“每次选能选的最大面额”这个贪婪直觉，得到的是 4 + 1 + 1 = 3 枚，但最优解是 3 + 3 = 2 枚。从此以后，我每道贪心题都会强迫自己先做一件事：能不能构造一个简单反例？如果能，直接换思路。这个动作花不了几十秒，但能帮你避开一大半错误解法。
要练习“证明直觉”，可以学一下交换论证法：假设存在一个最优解 S，其中某一步的选择和贪心选择 g 不同；证明把 S 中那一步换成 g 后，结果不会比 S 差，那么贪心选择一定存在于某个最优解中。听起来复杂，但实际做几道题后会变成一种自然反应。比如 452 题，你其实是在证明“把箭放在最右端点不会比放在更左边差，因为最右端点能覆盖所有和当前区间重叠的区间”。
5.2 排序方向、边界条件和累加溢出
贪心题里排序方向堪称重灾区。我的经验是：
- 区间贪心类（452、435、763）：优先按右端点排序。因为你想让“结束早的区间先被处理”，给后面留更多空间。
- 合并区间类（56）：按左端点排序。因为你要尽量把一个区间往后扩张，如果按右端点排，会出现左端点大但右端点小的区间先被处理，导致合并逻辑混乱。
- 普通分配类（455、135）：按值本身排序，通常升序。
边界条件上，跳跃游戏 II 循环到 n-1 为止，否则多算一步；452 题如果两区间首尾相接 start == cur_pos，也要算作一支箭可以覆盖，只有 start > cur_pos 才需要新箭；135 分发糖果两次遍历时，第二次从右往左必须用 max 保留第一次遍历的结果，不能直接覆盖。
至于溢出，Python 写起来没压力，但如果你是 C++ 或 Java 选手，股票类题目累加利润时注意用 long，区间端点求和或排序时也要留意整型范围。Hot 100 这类基础题一般不会卡精度，但养成用 long 的好习惯没坏处。
5.3 调试技巧与模板
如果一道贪心题提交后 WA，别急着怀疑思路，先打印每一步的决策变量。拿 45 跳跃游戏 II 举例，你可以把每一步的 i、farthest、cur_end、jumps 都打出来，然后和手推的样例对比。绝大多数错误集中在“步数更新时机”和“最远位置更新顺序”上。
另一个很实用的技巧是写一个对比验证函数：在本地用暴力 DFS 或 DP 实现同一道题，随机生成小规模数据，把贪心结果和暴力结果不断对拍。这个过程不一定要提交，但能非常高效地验证你的贪心策略是否真的正确。我刷中等难度的贪心题时，基本都会先写这个对拍脚本，跑几千组随机数据再交。不能说万无一失，但至少能把 90% 的低级错误挡在提交之前。
5.4 一套能直接抄的贪心题自检清单
刷完之后我把自己的检查流程整理成清单，分享出来：
- 题目求的是不是“最大/最小/最少/最多”这类极值？
- 我提出的策略每步是不是只看当前状态做出唯一选择？
- 这个选择会不会影响未来状态，并且影响方式是不是只有一种？
- 我用示例和自己构造的反例验证过吗？
- 如果面试官问“为什么贪心对”，我能说出交换论证或反证的关键步骤吗？
- 代码里有没有排序方向错误、边界多算少算、数据类型溢出的隐患？
只要这几点都过了一遍，我就敢提交。如果某一条不满足，马上转向 DP、二分或 DFS。
我个人刷完 Hot 100 贪心题后最强烈的体会是：贪心本身不难，难的是克制自己“想当然”的冲动。每次你觉得“这题肯定贪心”的时候，先花一分钟想反例；每次你觉得“这题要 DP”的时候，也先想一想是不是有一个更简单的单调维护变量能直接用。把这两种思维来回切换练熟了，你在面试时遇到新题就不会慌，因为你能很快判断该走哪条路。最后再分享一个小技巧：把 2.6 里那张表格贴在自己笔记里，每次刷到新题先试着归类到某一类里，归类准确率就是你贪心水平的晴雨表。
