1. Hot100里的贪心专题，值得你单独拿出来刷一遍
LeetCode Hot100这个题单，我前后刷了三轮。第一轮是跟着题号硬啃，第二轮按标签分类，第三轮才开始真正按专题拆。做到“贪心专题”这一块的时候，我突然意识到：Hot100里的贪心题其实特别适合作为判断“算法思维成熟度”的试金石。它不像动态规划那样动不动就状态转移、空间压缩，也不像图论那样上来就是模板和板子。贪心题表面看谁都看得懂——选个局部最优，然后祈祷全局最优——但真正动手AC之后，你会发现坑全藏在证明和选择策略里。
这个专题适合谁？我说句实在话：已经开始刷Hot100、但经常在“这题到底能不能贪心”上卡住的同学，这篇文章就是给你准备的。如果你刚接触算法题，建议还是先把数组、链表、二叉树这些基础专题刷稳，再回来碰贪心。但如果你的目标是面试中的“中等难度贪心题不丢分”，那Hot100里的这些题就是最好的训练场。
很多人把贪心理解成“感觉对就写”，这是最大的误区。真正拉开差距的，是你能不能快速判断一道题是否具备贪心选择性质，能不能在写完解法后用一句话把正确性讲明白。Hot100里涉及贪心的题不算多，大概十几道，但每一道都代表了贪心领域的一个典型模型：状态记录型、最远可达型、区间覆盖型、差值累加型。把这十几道吃透，比盲目刷两百道剑指Offer的碎片题有用得多。
我实测下来，Hot100的贪心题主要集中在三类场景。第一类是“序列决策类”，典型的比如买卖股票的最佳时机、跳跃游戏；第二类是“区间打交道类”，无重叠区间、用最少数量的箭引爆气球这类排序后贪心；第三类是“分配类”，分发饼干、分发糖果这种。你会发现这三类的思考方式完全不一样，但它们共享同一个底层逻辑——局部最优策略能否递推成全局最优。这篇文章我就按这个底层逻辑来拆。
2. 贪心的底层逻辑：先搞懂“为什么能贪”，再去背题
2.1 贪心选择性和最优子结构，才是真正的考点
《算法导论》里讲贪心算法，必提两个概念：贪心选择性和最优子结构。我当年看教材这里睡了三次，后来刷题刷多了才明白，这两个词翻译成人话就是：
- 贪心选择性：你做每一步的“当前最优选择”时，不需要回头考虑之前的选择会不会耽误全局。
- 最优子结构：你把一个大问题切掉一块之后，剩下的小问题仍然可以用同样规则来解。
对应到Hot100的具体题目里，最典型的例子是跳跃游戏（55题）。它的核心做法是维护一个能跳到的最远位置，每走一步就更新这个变量。为什么这能保证最终判定正确？因为“能到达的最远位置”只取决于当前可达的所有位置中能跳得最远的那个，而不取决于你具体走了哪条路径。每判断一个位置，都是独立地把“当前能触达范围”往外扩，这个子问题用同样的贪心规则持续求解，就是整个题的解。
再比如买卖股票的最佳时机II（122题），做法更简单：只要今天的价格比昨天高，就昨天买入、今天卖出，累加所有正向差价。为什么可以这么做？因为总利润可以被拆解成相邻两天的差价之和，而且每个正向差价都是独立可取的。局部看“今天比昨天贵就赚这笔”是最优的，全局看所有正向差价相加就是最大收益，两者完全一致。
反过来说，一道题的难点就在于“局部最优是否能串成全局最优”并不总是直观。我记得第一次做**跳跃游戏II（45题）**时，我想当然地写了一段“每次都跳到能跳得最远的位置”的代码，一提交直接WA。原因很简单：最远位置不等于最优解，你还需要保证下一步还能继续走远。这里的贪心对象其实不是“一个点的最远位置”，而是“当前一步的跳跃范围内，下一步能到达的最远位置”。你看，同样是“维护最远位置”，定义差一个字，正确性就完全不一样。
2.2 贪心和动态规划的分界线，是你选择策略的底气
很多人问到底什么情况用贪心，什么情况用DP。我的经验是：动态规划面对的是“局部最优可能影响后续选择”的场景，贪心面对的是“局部最优不会影响后续选择”的场景。换句话说，贪心是DP的一种特例，只不过贪心把状态压缩成了“当前一步的最优决策”而已。
Hot100里有一道题特别适合说明这个分界线：分发糖果（135题）。题目要求相邻评分高的孩子必须拿更多的糖。如果你只从左往右扫一遍，没法确定结果；只从右往左扫一遍，也没法确定。一定要从左到右处理一遍“右边比左边高就加一”，再从右到左处理一遍“左边比右边高就加一”。这其实已经带了一点DP的味道，但它仍然属于贪心，因为每一次比较都只针对相邻两个元素，不依赖于更早的全局状态。最终取两边结果的最大值，这也是经典的“两次遍历贪心”。
还有个更常见的识别技巧：如果题目求的是“最大/最小”且只要求一个数值结果，先想能不能排序。一排完序，很多局部决策就变得理所当然。Hot100里的无重叠区间（435题）、用最少数量的箭引爆气球（452题），都是先排序再做贪心。注意排序的维度很关键，是按左端点排还是按右端点排，直接决定了你能不能顺利证明。这就引到下一个部分。
3. Hot100贪心题的实操拆解：读题、选策略、AC
3.1 买卖股票系列：差价累加和一次遍历的由来
先把Hot100里涉及股票的题放一起看：121题只能买卖一次，122题可以无限次买卖，两个题解法完全不同，但放到一个专题里刷，你才能懂贪心在不同约束下是如何演化的。
121题，买卖股票的最佳时机，要求一次买卖的最大利润。这题其实不一定要用贪心，很多人的第一反应是动态规划，但其实一次遍历就够了：维护一个“当前出现过的最低价格”，然后每到一个新价格，就用它减去最低价，跟历史最大利润比大小。
def maxProfit(prices): 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这里为什么是贪心？因为你在遍历过程中做出的决策只有两个状态：要不要更新最低价、要不要更新最大利润。更新最低价不会影响之后利润的计算——反正后面永远可以用更低的成本去重新计算收益。你不需要知道最低价是哪一天，只需要知道“到当前天为止最低的价格是几”。这种“边遍历边记录最优历史状态”的写法，就是贪心里的“状态记录型”。
122题，买卖股票的最佳时机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我第一次做这题的时候其实有个疑惑：如果今天买明天卖，后天再买大后天卖，中间会不会错过“从昨天直接持有到大后天”的大涨？答案是根本不会。因为那一段大涨幅的利润可以被拆成逐日差价的累计和。连续持有N天的总收益，等于中间N段相邻差价的代数和。所以把每一天的正差价都收进口袋，等价于在所有上升段里都有仓位。这就是“差值累加型”贪心。
3.2 跳跃游戏系列：维护最远可达距离的边界价值
接下来是跳跃游戏两道题。说实话，我刷Hot100时最怕遇到这种“题目描述很简单，解法也不难，但总觉得自己不够理解”的题。55题是判断能否到达最后一个位置，45题是求到达最后一个位置的最少跳跃次数。两题都是“最远可达型”贪心的代表。
55题的核心就是维护一个max_reach。从头开始遍历，如果i > max_reach就说明当前脚够不着，直接返回False。否则用max(max_reach, i + nums[i])来更新。遍历结束返回True。为了更好理解，我建议你想象一根橡皮筋，你每走到一个新格子，就把橡皮筋往右拉长到它能拉到的极限。橡皮筋覆盖到的所有格子都是“可达区间”，一旦遍历到橡皮筋外面，绳子断了，自然到不了终点。
45题比55题难在要求最小跳跃次数。网上很多题解直接给“贪心区间”解法，但没解释为什么有效。我自己刷的时候是这么推导的：
- 定义
current_end为当前这一跳最远能到的位置，farthest为在当前区间里所有位置再跳一步后能到达的最远位置。 - 从头遍历，每到一格就尝试更新
farthest = max(farthest, i + nums[i])。 - 当
i跑到current_end时，说明这一跳的区间已经冒完，不得不发起下一跳。此时jump += 1，并把current_end更新成farthest。这其实就是下一跳的可达范围。
def jump(nums): n = len(nums) jumps = 0 current_end = 0 farthest = 0 for i in range(n - 1): farthest = max(farthest, i + nums[i]) if i == current_end: jumps += 1 current_end = farthest if current_end >= n - 1: break return jumps为什么在区间边界才跳，而不是在“看到最远的那个点”就跳？因为跳跃次数只关心你在某个区间内完成了“起跳”，不关心从哪一格起跳。你只需要知道“目前这段我能蹦到的位置里，时刻盯着谁跳得最远，一旦到了不得不跳的时刻，选最远那个思路走”。这也是贪心选择性的体现——每段区间内选择最远推进方向，整个序列的跳跃次数就最小。
3.3 区间类贪心：排序规则选错了，代码写得再漂亮也白搭
Hot100里的区间题是这个专题里最容易拿分的类型，因为它们有一个通用套路：排序 + 按某种规则局部排除。但也最容易踩坑，因为排序规则一旦选错，整个贪心策略的证明就崩了。
先说无重叠区间（435题）。题目的意思：去掉最少的区间，让剩下的区间互不重叠。
常规解法是按右端点升序排序，然后从左到右扫，如果当前区间的左端点小于上一个保留区间的右端点，就删掉当前区间（即计数加一）。为什么按右端点排序而不是左端点？这其实是区间贪心里一个屡试不爽的结论：按右端点排序后，越早结束的区间，越不占地方，越有可能给后面的区间留出空间。你留出的空间越大，最终能保留的互不重叠区间就越多。
按左端点排序为什么不行？我举个反例给你看：区间[3, 9]和[4, 5]出现在你面前，按左端点排[3,9]先被处理，保留它的话，[4,5]就得删掉。但如果先把[4,5]留下，[3,9]里有一部分可以用，反而可以再塞进别的短区间。你可以实际跑一个样本：[[3,9],[4,5],[6,8]]，就会发现左端点排序会让结果多删一个区间。这就是“排序维度决定贪心策略能否自洽”的典型案例。
再来看用最少数量的箭引爆气球（452题）。其实它和无重叠区间是同一个模型的正反面。排序依然是按右端点升序，每射出一支箭，就把它定位在某个气球的右边界，然后一路穿透所有“左边界小于等于这个右边界”的气球。这里有个非常容易忽略的边界条件：两个气球的边界刚好相切，即前一个的end等于后一个的start时，一支箭可以同时引爆它们。所以判断条件必须是start > prev_end才需要新箭，而不是>=。我第一次刷的时候用了>=，直接多射了好几只箭进去。
3.4 加油站和划分字母区间：两个被低估的贪心细节
**加油站（134题）**是Hot100里一道容易让人放弃的题，因为“绕着圈走”这个设定很容易让人想到环形数组、取模运算。但我告诉你，它的贪心解法和跳跃游戏二有异曲同工之妙。
核心思路是：把所有gas[i] - cost[i]的差值累加，如果全程总消耗大于总补给，直接返回-1。否则，从某个起点开始，维护一个当前油量，一旦当前油量变成负数，就把起点强制设为下一个站点，并重置油量计数。为什么这能保证找到唯一解？因为当你在i到j之间发现油量不够时，说明从i到j之间的任何一个站点出发都会在这个区间内失败。基于这个排除性质，你只需要从失败段的后一个点重新开始扫描。
这个题有个细节我踩过坑：(总剩余为负数直接返回-1)实际上可以优化成先循环一遍算总剩余，但更顺滑的写法是遍历一遍时同时记录总剩余和当前剩余。有人把这两种逻辑写岔，导致起点判断出错。我个人的建议是分两个变量写清楚：total_gas管全局能否跑通，current_gas管局部起点是否有效。两个变量同步维护，代码的可读性和正确性都会高很多。
**划分字母区间（763题）**是另一种贪心模型，但它不排序，而是先扫描一遍字符串，记录每个字母最后出现的位置。然后再扫第二遍，用一个right变量不断扩张当前段落的右边界，当遍历到了这个边界时，立即切出一段。
我第一次做这题时，只顾着记每个字符出现的次数，结果发现切分条件根本没法判断。后来才悟到：这里贪心的对象不是“出现次数”，而是“最后一个位置”。两遍扫描本质上就是先收集全局信息，再局部贪心决定切分点。“先全局信息预处理，再线性扫描构造段”的做法，在字符串贪心题里非常常见，Hot100里的这题是入门最好的样本。
4. 这专题最坑的四个地方：我的刷题教训和排查思路
4.1 贪心失败时，先证明再改代码
我对所有初学贪心的朋友建议都一样：写代码之前，先用一句话写出“为什么局部最优会等于全局最优”。如果你写不出来，那大概率不是代码问题，是策略问题。
举个我自己的真实案例。有一段时间我做区间类题目，每次都自作聪明地按“区间长度最短优先”排序，结果在很多重叠场景下都得不到最优区间集合。后来我发现，这种策略只能保证“当前选择最短区间不碍事”，无法保证“剩下的部分还能不能用同样的规则处理”。这就是典型的“没有最优子结构”的局。其实用反例就能验证——你构造一组大小不一、互相重叠的区间，把每个区间画在数轴上，稍微重叠几次，就会找到反例。
所以排查贪心问题的第一步不是去debug，而是构造一个小规模样例，自己手动推演一遍。只要你能找到一个反例证明贪心策略不成立，那就说明要么策略定义错了，要么这题压根不该用贪心而应该用DP。
4.2 边界条件和排序方向，是两类最高频的Bug来源
Hot100贪心题的典型边界条件我随手就能列一堆：
- 122题：价格数组长度为1时，循环不会执行，利润就是0，没问题。
- 45题：数组长度恰为1时，实际上不需要跳跃，所以循环变量应该排除最后一位。
- 452题：两个气球的边界相切时，是否算一支箭能同时引爆，这是最容易错的地方。
- 763题：字符串只有一个字母时，切分结果应该是一整个字符串，注意边界初始化。
- 134题：总剩余为零时，结果是最后一个“失败段后”的起点，很多人在这道题上被
while循环绕晕，忘了用单次for扫描代替复杂的环形模拟。
如果你AC不了，先用小规模测试用例把边界跑一遍。很多时候WA不是思想问题，就是处理n=1或者“边界相等”时的运算符写错。我在公司带新人刷题时，反复强调：刷题最忌讳一遍提交失败之后盲目乱改，你要改的是边界条件，不是整体算法。
4.3 明明想的是贪心，为什么AC的是动态规划
刚才我说贪心是DP的特例，但Hot100里有些题目你看着像贪心，实际上偷偷需要用动态规划。比如最长递增子序列这类题目，它的局部最优就无法直接确定全局最优——你选了一个短序列，可能因为它最后一个元素小，反而给后面留出更多空间。这其实也是一个经典的陷阱题。
面对这种题，我的建议是看到一个题目先做“约束条件分析”：
- 如果题目约束满足“子问题的最优解包含在全局最优解里”，可以贪心。
- 如果题目需要记录多个可能的状态才能比较出结果，那大概率得DP。
用这个尺度去量Hot100的贪心专题，你会发现所有真正的贪心题都满足一个简洁特征：决策之间不产生互相制约。反过来，你一旦发现“这一步选了A，下一步就只能选B”，这通常意味着存在约束传播，贪心就不再适用。
4.4 调试时用“打印策略”代替“默想”
我当时刷Hot100贪心题时，有一个特别管用的调试技巧：在关键决策点打印当前策略和维护变量。比如跳跃游戏二里，每次走到current_end时就打印当前farthest和跳跃次数。一眼就能看出算法是不是在正确的位置跳了。这个方法尤其适合那些“代码跑得通但答案不对”的情况，因为你不需要盯着变量在脑子里模拟，直接把过程打印出来，对不上就说明策略有问题。
还有一个偏方：用暴力解法做交叉验证。贪心题的数据范围一般都不大，尤其是Hot100里的这些题，你完全可以直接写一个深度优先搜索或者回溯作为“标准答案”，然后随机生成一堆小规模测试数据，把贪心结果和暴力结果对比。这个方法看起来土，但我实测下来比任何测试用例都好用。随机数据里最容易暴露反例。
5. 关于刷题顺序和投入产出的个人建议
我自己的做法是把Hot100的贪心专题分成三个梯队来刷：
- 第一梯队：121、122、55。这三道题覆盖了“状态记录”和“最远可达”两个基本模型，代码量小，适合建立信心。
- 第二梯队：45、134、763。这三道题需要你理解“区间边界”和“全局排除法”，是真正的贪心思维分水岭。
- 第三梯队：435、452、135。这三道题是区间分配和两次遍历的代表，面试里出现频率极高，值得反复练习。
如果你时间有限，优先把第一梯队和第三梯队刷透。第二梯队里的134题确实需要多想一点，但它的模型比较独特，即使面试遇到也有更通用的模拟解法兜底。
最后分享一个我反复踩坑后总结出来的核心心法：不要试图背下每道贪心题的具体代码，而是记“这道题的贪心对象是什么”以及“为什么这个对象的局部最优等于全局最优”。比如121的贪心对象是“历史最低价”，55的贪心对象是“可覆盖的最远边界”，435的贪心对象是“当前区间右端点的位置最小化”。把每个题抽象成一句话，遇到新题时再去套有没有对应的模型。那时候你会明显感觉到，Hot100的贪心专题不是散的，而是一张有规律可循的知识网。
我三次刷Hot100，前两次都是题目AC了就过，第三轮才专门把贪心拿出来复盘，收获反而比前两轮加起来都大。贪心题属于那种“代码写起来痛快、解释起来费劲”的类型，但正是这份费劲，才逼着你把算法的底层逻辑真正想明白。希望这篇拆解能帮你少走点弯路。
