1. Hot100里的贪心专题值得你单独拿出来刷一遍LeetCode Hot100这个题单我前后刷了三轮。第一轮是跟着题号硬啃第二轮按标签分类第三轮才开始真正按专题拆。做到“贪心专题”这一块的时候我突然意识到Hot100里的贪心题其实特别适合作为判断“算法思维成熟度”的试金石。它不像动态规划那样动不动就状态转移、空间压缩也不像图论那样上来就是模板和板子。贪心题表面看谁都看得懂——选个局部最优然后祈祷全局最优——但真正动手AC之后你会发现坑全藏在证明和选择策略里。这个专题适合谁我说句实在话已经开始刷Hot100、但经常在“这题到底能不能贪心”上卡住的同学这篇文章就是给你准备的。如果你刚接触算法题建议还是先把数组、链表、二叉树这些基础专题刷稳再回来碰贪心。但如果你的目标是面试中的“中等难度贪心题不丢分”那Hot100里的这些题就是最好的训练场。很多人把贪心理解成“感觉对就写”这是最大的误区。真正拉开差距的是你能不能快速判断一道题是否具备贪心选择性质能不能在写完解法后用一句话把正确性讲明白。Hot100里涉及贪心的题不算多大概十几道但每一道都代表了贪心领域的一个典型模型状态记录型、最远可达型、区间覆盖型、差值累加型。把这十几道吃透比盲目刷两百道剑指Offer的碎片题有用得多。我实测下来Hot100的贪心题主要集中在三类场景。第一类是“序列决策类”典型的比如买卖股票的最佳时机、跳跃游戏第二类是“区间打交道类”无重叠区间、用最少数量的箭引爆气球这类排序后贪心第三类是“分配类”分发饼干、分发糖果这种。你会发现这三类的思考方式完全不一样但它们共享同一个底层逻辑——局部最优策略能否递推成全局最优。这篇文章我就按这个底层逻辑来拆。2. 贪心的底层逻辑先搞懂“为什么能贪”再去背题2.1 贪心选择性和最优子结构才是真正的考点《算法导论》里讲贪心算法必提两个概念贪心选择性和最优子结构。我当年看教材这里睡了三次后来刷题刷多了才明白这两个词翻译成人话就是贪心选择性你做每一步的“当前最优选择”时不需要回头考虑之前的选择会不会耽误全局。最优子结构你把一个大问题切掉一块之后剩下的小问题仍然可以用同样规则来解。对应到Hot100的具体题目里最典型的例子是跳跃游戏55题。它的核心做法是维护一个能跳到的最远位置每走一步就更新这个变量。为什么这能保证最终判定正确因为“能到达的最远位置”只取决于当前可达的所有位置中能跳得最远的那个而不取决于你具体走了哪条路径。每判断一个位置都是独立地把“当前能触达范围”往外扩这个子问题用同样的贪心规则持续求解就是整个题的解。再比如买卖股票的最佳时机II122题做法更简单只要今天的价格比昨天高就昨天买入、今天卖出累加所有正向差价。为什么可以这么做因为总利润可以被拆解成相邻两天的差价之和而且每个正向差价都是独立可取的。局部看“今天比昨天贵就赚这笔”是最优的全局看所有正向差价相加就是最大收益两者完全一致。反过来说一道题的难点就在于“局部最优是否能串成全局最优”并不总是直观。我记得第一次做**跳跃游戏II45题**时我想当然地写了一段“每次都跳到能跳得最远的位置”的代码一提交直接WA。原因很简单最远位置不等于最优解你还需要保证下一步还能继续走远。这里的贪心对象其实不是“一个点的最远位置”而是“当前一步的跳跃范围内下一步能到达的最远位置”。你看同样是“维护最远位置”定义差一个字正确性就完全不一样。2.2 贪心和动态规划的分界线是你选择策略的底气很多人问到底什么情况用贪心什么情况用DP。我的经验是动态规划面对的是“局部最优可能影响后续选择”的场景贪心面对的是“局部最优不会影响后续选择”的场景。换句话说贪心是DP的一种特例只不过贪心把状态压缩成了“当前一步的最优决策”而已。Hot100里有一道题特别适合说明这个分界线分发糖果135题。题目要求相邻评分高的孩子必须拿更多的糖。如果你只从左往右扫一遍没法确定结果只从右往左扫一遍也没法确定。一定要从左到右处理一遍“右边比左边高就加一”再从右到左处理一遍“左边比右边高就加一”。这其实已经带了一点DP的味道但它仍然属于贪心因为每一次比较都只针对相邻两个元素不依赖于更早的全局状态。最终取两边结果的最大值这也是经典的“两次遍历贪心”。还有个更常见的识别技巧如果题目求的是“最大/最小”且只要求一个数值结果先想能不能排序。一排完序很多局部决策就变得理所当然。Hot100里的无重叠区间435题、用最少数量的箭引爆气球452题都是先排序再做贪心。注意排序的维度很关键是按左端点排还是按右端点排直接决定了你能不能顺利证明。这就引到下一个部分。3. Hot100贪心题的实操拆解读题、选策略、AC3.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不是思想问题就是处理n1或者“边界相等”时的运算符写错。我在公司带新人刷题时反复强调刷题最忌讳一遍提交失败之后盲目乱改你要改的是边界条件不是整体算法。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了就过第三轮才专门把贪心拿出来复盘收获反而比前两轮加起来都大。贪心题属于那种“代码写起来痛快、解释起来费劲”的类型但正是这份费劲才逼着你把算法的底层逻辑真正想明白。希望这篇拆解能帮你少走点弯路。