★ FEATURED ARTICLE 1. 从Hot 100看贪心专题会做几道题不算会能识别贪心场景才算入门先把话说在前面我在刷完Hot 100题单里那些打上贪心标签的题目之后最大的感受不是这些题简单而是这可能是整个刷题过程中最难稳定得分的一类题。原因很简单——贪心算法没有一个固定的套路模板不像二分查找有区间收缩、不像动态规划有状态转移方程它更像是一种决策直觉而直觉是会骗人的。回顾Hot 100的题单分布贪心专题的题目数量不算多但每一道都极具代表性分布在股票买卖、跳跃游戏、区间调度、任务分配等场景里。它们的共同特征是每一步只需要做当下看起来最好的选择并且这种选择在全局上也是最优的。但难点恰恰在于——你怎么知道当下最好等于全局最好这个问题的答案就是贪心算法的灵魂所在。这篇文章想把Hot 100里的贪心专题拆开讲清楚。我会结合这些题目共同考查的核心能力聊聊什么类型的题适合用贪心、哪些经典场景在Hot 100里反复出现、每类题目背后的数学逻辑是什么以及我在刷题过程中踩过的判断失误和总结出的验证技巧。无论你是刚开始刷题的小白还是正在准备面试、想系统梳理贪心题型的人这篇文章都值得花二十分钟读完。2. 贪心题的本质如何快速识别这道题可以贪心很多人在刷题时有一个误区觉得贪心题就是凭感觉选一个局部最优解代码写完能过样例就算完。但真正遇到一个全新的题目核心难点从来不是写代码而是你怎么知道这道题能用贪心2.1 贪心算法的两个核心性质任何能用贪心解决的问题理论上都需要满足两个性质贪心选择性质和最优子结构。贪心选择性质指的是通过一系列局部最优的选择最终可以拼出全局最优解。听起来像废话但操作起来很严格——你要证明在当前状态下做出的最优选择永远不会妨碍后续步骤达到全局最优。举个例子在跳跃游戏里每一步选择跳到能到达的最远位置这个选择不会让后续的可达范围变小因此成立。最优子结构指的是一个问题的最优解包含其子问题的最优解。也就是说每次贪心选择之后剩下的问题仍然是同类型的子问题并且可以继续用同样的策略求解。这两个性质听上去抽象实际判断时有一个非常实用的土办法试着构造反例。如果你能在脑子里画出一个场景让每步都取局部最优最终得到的结果比刻意牺牲某一步更差那这道题基本不能用贪心。反之如果无论如何构造反例局部最优都能导向全局最优那贪心大概率可行。2.2 贪心与动态规划的分界线Hot 100里有一类题特别容易让人犹豫就是求最大值/最小值的题目。这时贪心和动态规划都能上桌选哪个靠什么判断经验告诉我一个分界线——当前选择是否会影响后续状态的可选择性。如果当前选择会改变后续面临的状态空间比如选了A就不能选B、选了今天卖就不能今天买这类题通常需要动态规划因为全局最优解依赖决策路径的组合。如果当前选择只是从多个可行选项中挑一个收益最大的选完不改变后续选项的集合和约束那就应该贪心。对比Hot 100里两道股票题就能看得很清楚只允许一次交易的版本状态依赖于哪一天买入、哪一天卖出的组合直接扫一遍记录历史最低价、每天计算潜在收益的做法本质上是在用遍历而非决策它之所以成立是因为线性扫描等价于枚举了所有可能的买卖组合中的最优者。而允许无限次交易的版本每一天的买入卖出互不影响累加所有上涨区间的差值就是全局最优这才是真正意义上的贪心。2.3 常见的贪心决策模型在Hot 100的题目范围里贪心场景其实可以归纳为几个反复出现的模型识别出模型就相当于有了解题的方向。第一个是差值累加模型代表题目就是股票收益最大化可多次交易。核心逻辑是只要今天的价格比昨天高就当成一次可实现的利润累加进去。它不关心哪段涨得最多只关心有没有涨涨了赚、跌了不亏。第二个是最远可达模型代表题目是跳跃游戏系列。核心逻辑是在当前位置能覆盖的所有下一步里选择一个能让整体覆盖范围最远的方向。跳跃游戏一只需要判断能否到达终点跳跃游戏二则需要计算最少步数两者本质上都在维护一个当前可达边界和下一步可达边界。第三个是排序后贪心模型代表题目是会议室占用无重叠区间这类区间题。区间题几乎逃不过排序要么按左端点排要么按右端点排排序完之后再用贪心策略逐个筛选。第四个是双指针配对模型代表题目是分发饼干分发糖果这类配对题。把两个序列排序然后用双指针做最优匹配每一轮都尽量用最小的代价满足最大的需求或者用最合适的资源满足最接近的需求。当你看到一个陌生题先别急着写代码套一下这四个模型。能对号入座说明贪心有戏完全对不上号就要谨慎了。3. 跳跃游戏系列最远可达思想为什么是贪心正确性的完美示范跳跃游戏是Hot 100贪心专题里最值得反复品味的题目没有之一。它表面考查的是数组遍历实际考查的是如何用一维扫描代替多分支搜索。3.1 跳跃游戏一维护最远可达位置题目不复杂给定一个非负整数数组每个数字代表你在当前位置最多能往后跳多远问能不能跳到最后一个位置。最朴素的想法是递归加记忆化——每个位置都有多种跳跃选择尝试每条路径。但稍微想一下就会发现每个位置能到达的最远下标是可以递推的最远可达 max(前一个位置的最远可达, 当前位置下标 当前位置的跳跃力)只要这个最远可达能覆盖到终点下标就说明存在一条路径。不需要关心具体怎么跳也不需要记录路径。代码量少得惊人function canJump(nums) { let maxReach 0; for (let i 0; i nums.length; i) { if (i maxReach) return false; maxReach Math.max(maxReach, i nums[i]); } return true; }我每次写这道题都会强调一个点判断条件i maxReach是核心中的核心。如果当前位置已经超出了历史能到达的最远范围说明你根本走不到这里自然无法继续往后跳。这个判断比最后看 maxReach 是否大于等于 nums.length - 1更早暴露问题也更符合直觉。3.2 为什么每次选最远是安全的很多人会质疑每次都从当前可跳范围内选最远的位置跳万一最远的那个位置落点很差比如跳跃力是0反而错过了一个稍近但后续更强的位置怎么办这里藏着一个关键洞察贪心策略根本不需要真的跳到最远位置。我们维护的 maxReach 只是一个可达范围边界它表示的是从起点出发经过一系列跳跃最远能触及的下标。在从左到右的扫描过程中只要 i 落在 maxReach 之内就说明位置 i 一定是可达的——无论你之前选择了哪条路径。换句话说每一個位置的潜力在扫描到它的时候都会被纳入边界计算中。即便某个位置跳跃力是0它已经对 maxReach 没有贡献但它自身被覆盖这件事说明之前的路径是有效的。这就是贪心选择性质在这个问题里的体现——任何局部选择都不会缩小可达范围因此选择最大扩展的那一个不会丢失任何潜在解。3.3 跳跃游戏二最少步数里的层序推进思想跳跃游戏二升级为计算最少跳跃次数Hot 100里同样高频出现。一开始我尝试用动态规划状态转移方程很容易写dp[i] min(dp[j] 1)其中 j 能一步到达 i。数据量小能过但遇到大数组就超时了——这提醒我动态规划的 O(n^2) 在这里并不是最优解。正确的姿势是贪心加层的概念。你可以把它想象成 BFS 层序遍历currentEnd表示当前这一层能到达的最远边界nextMax表示在边界内所有点进一步跳跃能到达的最远位置。当 i 扫到 currentEnd 时说明必须再跳一次步数加一同时把 currentEnd 更新为 nextMax。function jump(nums) { let steps 0; let currentEnd 0; let nextMax 0; for (let i 0; i nums.length - 1; i) { nextMax Math.max(nextMax, i nums[i]); if (i currentEnd) { steps; currentEnd nextMax; } } return steps; }这个算法的精妙之处在于它完全没有指定具体跳到哪个位置而是把所有位置按需要几步跳到这里分层每一层结束时自然更新边界。步数对应的是跨越层边界的次数而 nextMax 永远取当前层内所有玩家的最大覆盖。这种做法的时间复杂度是 O(n)是 Hot 100中等难度题里难得一见的高效解法。提示跳跃游戏二有个细节容易写错——循环终止条件是i nums.length - 1而不是i nums.length。因为终点本身不需要再跳如果让 i 遍历到最后一个下标可能会在不需要跳跃的情况下额外增加一次步数。4. 股票买卖与区间调度差值累积和排序后贪心的两种典型范式跳跃游戏之后Hot 100贪心专题里频率最高的就是两类题一类是股票买卖一类是区间调度。它们的解题范式截然不同但都极具复用价值。4.1 股票买卖允许多次交易为什么累加正差值就够了先说股票多次交易版本。很多人第一次看到将每个上涨段累加的解法时会觉得太取巧我也一样心里嘀咕万一某天卖了之后价格继续涨不是少赚了吗答案是这个做法根本不需要卖。它实际上是每天都在做决策——如果今天的价格比昨天高就视为昨天买入、今天卖出赚取这一个单位的差价如果今天比昨天低就不操作。每次赚取的只是相邻两天的正差值所有正差值相加等于所有上涨区间的收益总和而任何一次跨越下跌段的持有都会减少总收益因此这组相邻正差价的集合天然就是全局最优解。这种思路把多次交易的复杂决策拆解成了每个单日决策的独立问题每个单日决策互不干扰满足了贪心的条件。实现代码只有三五行def max_profit(prices): profit 0 for i in range(1, len(prices)): if prices[i] prices[i - 1]: profit prices[i] - prices[i - 1] return profit4.2 无重叠区间按右端点排序的直觉解释区间调度问题在Hot 100里通常以移除最少区间使剩余区间互不重叠的形式出现。等价转换一下就是最多保留多少个互不重叠的区间。这类题的关键决策在排序维度上。如果按左端点排序你会在区间头部排成一串之后发现每次选左端点最小的可能选到一个右端点极大、覆盖一切的巨无霸导致后面所有区间都无法选。所以正确的策略是按右端点排序每次选择右端点最小的区间因为它对后续区间的挤压最小。这个策略的直观解释是右端点越小的区间结束得越早给后面的区间留出的空间越大。每选一个区间就更新当前已占用的最后边界然后跳过所有与之重叠的区间继续挑选下一个结束最早的区间。function eraseOverlapIntervals(intervals) { if (!intervals.length) return 0; intervals.sort((a, b) a[1] - b[1]); let count 1; let end intervals[0][1]; for (let i 1; i intervals.length; i) { if (intervals[i][0] end) { count; end intervals[i][1]; } } return intervals.length - count; }边界条件intervals[i][0] end是细节中的细节区间相邻前者的右端点和后者的左端点相等不算重叠这道题里可以直接保留不用更新 end 的写法遇到相等情况会造成误删。4.3 合并区间与会议室问题排序后的贪心变体合并区间这道热题本质上也是排序后贪心的应用只是目标从移除重叠变成了融合重叠。按左端点排序后逐个检查新区间是否与当前合并区间的右边界重叠重叠就扩展右边界不重叠就输出当前合并区间并开始新的一段。我做这类题时喜欢用一个技巧先明确排序后哪些性质变得可以利用再考虑用哪种贪心策略。按左端点排序后重叠的区间必然连续分布只需线性遍历一次按右端点排序后可以得到最早完成的保证适合选择问题。想清楚排序的目的代码就不容易写偏。会议室类问题计算最多同时使用的会议室数量则是贪心的又一个变体——它需要对开始时间和结束时间分别排序然后用双指针扫描遇到开始时间就 count 加一、遇到结束时间就减一过程中 count 的最大值就是答案。这个做法跳跃性比较大我第一次看的时候觉得像是技巧题但后来意识到它的本质是事件扫描比堆排序的实现更直观、更快。5. 配对的贪心分发饼干与分发糖果里的排序直觉Hot 100里还有一类很适合练手但容易被低估的贪心题——配对类题目。它们的特征是两个序列之间建立最优匹配考察的是如何通过排序把复杂匹配转化为线性扫描。5.1 分发饼干局部最优如何通向全局最优题目背景很简单每个孩子有一个饥饿度每块饼干有一个尺寸只有饼干尺寸大于等于孩子的饥饿度时孩子才能满足。问最多能满足几个孩子。这个问题的直觉是尽量让每个孩子吃到的饼干刚好够饱而不是浪费大饼干满足小饥饿度。所以正确做法是两个数组都排序然后从饥饿度最小的孩子开始用双指针寻找第一块尺寸足够的饼干喂给他。def find_content_children(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注意代码里j 1放在 if 外面——即使饼干不够大也要继续往后找不能停在原处。这个细节我一再提醒自己因为写错成匹配失败就不移动 j会导致死循环或漏掉后面的可用饼干。为什么排序后从小到大匹配是对的关键在于饥饿度最小的孩子是最容易满足的先满足他只需要消耗尽可能小的资源如果连最小的饼干都无法满足他那更大的饼干留给饥饿度更大的孩子只会更浪费。这种用最合适的资源满足最容易被满足的人的思路就是典型的排序后贪心。5.2 分发糖果两遍扫描处理依赖关系的技巧另一道口感完全不同的题是分发糖果每个孩子至少一颗糖相邻孩子中评分更高的必须拿到更多糖果问最少需要多少颗。我第一次看到这道题愣了很久——这明显存在左侧约束和右侧约束两个方向的限制无法一次性得出答案。正确的做法是拆成两个独立约束分别用两次贪心扫描解决。先从左往右扫保证每个孩子如果比左边邻居评分高糖果数比左边邻居多再从右往左扫保证每个孩子如果比右边邻居评分高糖果数比右边邻居多。每个位置的最终糖果数是两次扫描结果的最大值。def candy(ratings): n len(ratings) left [1] * n for i in range(1, n): if ratings[i] ratings[i - 1]: left[i] left[i - 1] 1 right [1] * n for i in range(n - 2, -1, -1): if ratings[i] ratings[i 1]: right[i] right[i 1] 1 return sum(max(left[i], right[i]) for i in range(n))这道题的价值不在代码而在思维面对多个方向的约束时可以先把约束拆开单独处理再合并结果。两遍贪心各负责一个方向合并时取最大值不会破坏任何一边的约束条件这就是约束分解的典型案例。6. 加油站点题与更复杂的贪心变体边界条件和起始点选择Hot 100里有一道加油站题经常被归类到贪心但它的思维路径和前面几类都不太一样值得单独拎出来说。6.1 总油量判断先行必要条件让问题瞬间简化题目给出每个加油站的油量 gas[i] 和从本站出发消耗的油量 cost[i]问是否存在一个起点能绕所有站点一圈回到原点。一个很容易被人忽略的数学事实是如果总的 gas 之和小于总的 cost 之和那么无论从哪里出发都不可能走完全程。这是必要条件也是解题的第一个剪枝。有了这个条件之后问题就变成了在总收益非负的序列中找一个合适的起点。6.2 为什么剩余油量最低点的下一个站是候选起点接下来是这道题最巧妙的贪心判断。从某个候选起点开始模拟维护当前剩余油量tank和当前累计剩余total。如果途中tank变成负数说明从这个起点出发无法到达当前站点接下来怎么做最符合直觉但效率较低的做法是换下一个起点重新模拟复杂度 O(n^2)。而贪心做法只用一次遍历当在站点 i 处 tank 小于0时把起点设为 i1并把 tank 清零重新累计。最终起点就是一个可行解。为什么可以这样跳原因是从原起点到 i 的任意一个中间站点 j从 j 出发都会在 i 处或更早出现剩余油量为负的情况。因为从起点到 j 的累计剩余油量是非负的否则之前就会触发重置。既然从起点出发、到达 j 时尚有油尚且无法越过 i那么从 j 出发、初始油量更低自然也无法越过 i。于是中间所有站点都可以一并排除。def can_complete_circuit(gas, cost): total 0 tank 0 start 0 for i in range(len(gas)): total gas[i] - cost[i] tank gas[i] - cost[i] if tank 0: start i 1 tank 0 return start if total 0 else -1我每次做这道题都会提醒自己必须先判断 total 是否非负再决定返回什么。如果总油量不足中途 tank 再正常都不能说明有解。这种先验证必要约束再贪心选点的组合思路在真实工作场景里也很常见——先排除不可能再寻找最优。6.3 一个容易忽略的贪心前置条件加油站这道题还有一个隐性前提每个站点到达下一个站点的过程是独立的也就是不会出现这次多留一点油就能改变后续局面的复杂耦合。这是因为任何加油站的油量都只能在到达时加不能提前预留所以每段路程的净消耗只取决于当前油量上限这保证了局部判断的独立性。如果题目改成可以选择不在某些站加油那问题就变成了背包或动态规划贪心就不成立了。很多时候我们觉得贪心题难是因为题目常常混入了看起来像贪心但实际不是的伪装成分。加油站题之所以是经典就是因为它恰好站在贪心可以解决和贪心会失效的分界线上。7. 实战复盘贪心题最常踩的坑与我的验证流程把Hot 100里的贪心题刷过几轮之后我发现这个专题真正考的其实是对反例敏感度和边界处理的能力。下面这些坑是我和身边朋友反复踩过的值得单独总结。7.1 局部最优不等于全局最优的典型反例很多初学者会在类似求最大上升子序列和或求最小字典序字符串的题目上尝试贪心结果发现局部最优拼不出全局最优。Hot 100中虽然没有专门刁难人的反例题但做题时仍然要有意识地问自己这一步选最值会不会导致后续可选空间变小以区间调度为例如果脑子一热选择按长度排序先选最短的区间就会出问题——一个最短的区间可能恰好横亘在中间阻断两侧所有区间而一个较长但靠边的区间反而能给更多区间腾地方。这正是局部最优短不等于全局最优多的典型反例。遇到这类选哪个更好的题我的第一反应永远是构造一个让它翻车的例子而不是急着写代码。7.2 排序方向错了整个解法就废了区间类问题的排序方向是另一个重灾区。按右端点排序和按左端点排序的贪心策略完全不同甚至可能得到相反结论。我有一个很简单实用的口诀如果目标是尽可能多选按右端点排序如果目标是合并范围按左端点排序。选择问题关注结束早不早合并问题关注开始早不早。这个口诀帮我避免过多次重复调试。做题时先想明白我要的是数量还是覆盖范围再确定排序字段基本不会跑偏。7.3 边界条件的细节清单贪心题代码普遍非常短短代码反而更容易在边界条件上翻车。我自己在刷Hot 100的过程中整理了一份适用度比较高的核对清单数组为空时函数是否直接返回正确默认值数组长度为1时是否存在越界访问遍历区间是i n还是i n - 1要看当前元素是否需要参与逻辑判断累积变量是否可能出现溢出使用 Number 或 Python 整型时一般不用担心但其他类型要注意排序后的首个元素是否需要单独初始化比较大小关系时是否允许相等区间相邻算重叠吗饼干大小等于饥饿度算满足吗。每道题在提交之前我都会用这些边界条件在脑子里把代码抽象地跑一遍。做完整套贪心专题之后这套检查流程的收益甚至超过了我背下来的粘贴板代码。7.4 三个验证贪心正确性的实用方法第一构造反例测试。在写代码前先尝试构造一个让策略失效的例子。如果构造不出来说明策略大概率没问题。第二暴力对拍。数据范围小的时候可以用递归或动态规划写一个纯暴力解法随机生成小规模测试数据和贪心解法的结果对比。这个习惯帮我抓住了至少三处隐藏的bug。第三数学归纳法论证。针对选择第一个元素的合理性通过归纳证明如果全局存在最优解则一定存在一个从贪心选择开始的全局最优解——这在学术上严谨在实际刷题中也能极大增强信心。提示贪心算法的复杂度通常非常优秀O(n log n) 已经算高的了主要由排序造成。如果你的贪心解法需要两层循环先停下来想想是不是选错了贪心策略或者这道题根本不能用贪心。8. 从Hot 100贪心专题延伸到真实场景的思考刷题的价值从来不只在通过率更在于迁移。Hot 100里的贪心题虽然在面试中只是算法题但它们背后的决策模型在工作场景中会以各种变形重新出现。8.1 广告投放与资源分配的贪心原型广告平台的预算分配就是一个典型的区间选优问题每个广告位有开始时间和结束时间每个广告主有预算希望在有限的广告位里尽可能服务更多高价值请求。按结束时间排序、优先选择能释放最多后续空间的请求是调度系统里最常见的优化策略之一。这和无重叠区间的解题思路完全相同。8.2 传输调度中的最远可达模型网络传输或者任务队列里的超时控制和跳跃游戏的 maxReach 模型也很像。每个任务能向后延伸处理的能力有一个上限调度器只需要维护一个当前任务链最远能覆盖到的进度即可判断系统是否可能卡死。这个判断方法比逐一模拟所有任务路径高效得多。8.3 事件驱动的计数器模型会议室问题中对开始和结束分别排序、事件扫描取峰值的思路也被广泛用在服务器并发连接数统计、客流峰值预测等场景中。你不需要逐个时刻去数只需要把事件的进入和退出分别排序一次扫描就能得到峰值。这是一种极其高效的近似统计方法。这些迁移案例想说明一件事贪心专题刷的不是题而是在约束条件下做最省资源的决策这一思维方式。当你建立了这种思维方式以后遇到新问题时会下意识地问有没有一个局部规则能让事情自动走向最优结局一旦这个问题成立代码往往就是几行的事。9. 最后分享一些我反复用到的实战技巧把Hot 100贪心专题完整过了一遍之后如果让我只留下三条最有价值的经验我会选下面这三条。第一不要背题解要背反例。贪心题代码太短背下来毫无意义真正值钱的是能证明你的策略不成立的反例长什么样。比如区间题里按长度排序的翻车案例、股票题里试图预测未来价格的幻觉——记住这些反例远比记住十行代码有价值。第二不确定能否贪心时先用暴力对拍验证。我刷题时养成了一个习惯只要对贪心策略有一丁点怀疑就写一个递归或动态规划的暴力版本随机生成一百组小规模数据跑对拍。虽然这会多花十分钟但换来的是对策略正确性的绝对信心。这个习惯尤其适合准备面试的冲刺阶段——面试官问你为什么贪心是对的你能答出数学论证回答因为我对拍过一百组随机数据也完全不丢人。第三警惕看起来能贪心的陷阱。一个题目只要出现子序列组合路径选择这类词汇就要立刻提高警惕。这些词暗示着决策之间存在耦合关系很可能需要动态规划而不是贪心。反过来题目如果强调每一步的收益独立可以无限次操作只需判断可行性那贪心的概率就大大增加。Hot 100里那些最经典的贪心题——跳跃游戏、股票买卖、无重叠区间、分发饼干、加油站——每一道都是浓缩的决策智慧。很多人觉得贪心是碰运气的算法我反而觉得它是最需要逻辑训练的一类算法。只有当你真正理解了为什么局部最优等于全局最优你才算在这个专题上入了门。希望这篇梳理能让你少走一些我走过的弯路。
阅读完成 · 觉得有帮助？
参数详解与数据清洗实战指南)
