1. 贪心到底是什么以及为什么你总是“差点想到但不敢写”我们直接切入正题。算法刷题这个领域贪心算法Greedy Algorithm一定在你的刷题计划表里占据一个特殊的位置。它不是数据结构那样有具体的形态不像 BFS、DFS 有清晰的模板它更像一种“做题时的决策策略”——在每一步都做当下看起来最好的选择并寄希望于这些局部最优的叠加能拼出全局最优。我见过太多人包括当年我自己在刷贪心题时卡在同一个心理关口题目能把样例过掉但总是不敢提交因为总觉得“这样选局部最优就能得到全局最优这也太玄学了”。这个想法很正常因为贪心的难点不在代码而在证明和勇气。代码往往不超过二十行但背后的取舍逻辑才是这道题真正考你的东西。这篇博文主要解决三个问题一是帮你看清贪心算法的底层决策逻辑二是从力扣高频题里拆出几种常见的贪心模型讲透每道题“为什么能贪”而不只是“怎么贪”三是梳理贪心与动态规划的分界线这是算法面试中一个非常高频的追问点。适合正在刷题准备面试的工程师也适合刚开始系统学算法、想真正理解贪心本质的同学。如果你之前只背过“贪心选择性质”和“最优子结构”这两个名词今天我们就把它彻底落到题目里。放心我不打算给你堆一屏定理下面全是用题目喂出来的实战认知。2. 贪心的核心支柱贪心选择性质与最优子结构2.1 为什么“局部最优”叠加起来会是“全局最优”很多人对贪心的怀疑是有道理的生活里“一步错步步错”的例子遍地都是凭什么在算法题里局部最优就能通关关键在于——能使用贪心的题目必须满足一个特殊的数学结构每一步的选择会对后续状态产生影响但这个影响的方向是“单向加强”的而不是“分叉发散”的。通俗地说就是你在第 i 步做出的选择无论后面怎么走都不会让之前的选择变成“负资产”。每一步都在当前剩余资源里挑最有利的动作而这个动作所消耗的资源边界恰好是给你后续选择留下最大余地的。这就是“贪心选择性质”。举个例子你用最少张数的纸币凑出指定金额如果你从最大面额开始凑每次选“当前能选的最大面额”最后用的张数就是最少的。因为大面额纸币永远是“被小面额替代不会更优”的所以局部选最大叠加起来就是全局最小张数。另一个支柱是“最优子结构”它说的是一个问题的最优解一定包含其子问题的最优解。贪心算法每次加工完一个局部剩下的部分仍然是一个独立子问题而且这个子问题的天花板并没有被之前的贪心选择压低。这两个性质放在一起构成了贪心算法能够成立的数学前提。但注意不是所有题目都这么听话。比如经典的“零钱兑换”问题如果货币面额是 1、5、11凑出 15 时贪心选择“先拿一张 11”会得到 11111 4 张但最优答案是 555 3 张。这里局部最优骗了你。所以刷贪心题第一件事不是写循环而是问自己这个选择后续会不会“翻旧账”如果会大概率该用动态规划。2.2 判断一道题能不能用贪心的三个实操标准正式刷题前我建议你脑子里固化一套“贪心三重门”的检查流程这套标准是我在自己刷了三百多道题后总结出来的适用范围非常广局部选择是否独立于剩余元素的相对顺序如果你把数组排序后重排元素不会影响最终结论题目往往暗示贪心可行。反之如果元素顺序本身承载了决策信息比如序列问题、子序列问题就要警惕。选择之后问题规模是否严格缩小为一个同构子问题每一步只需推进一个指针、消耗一个元素、关闭一个区间之后面对的是“剩余部分”的同类问题这说明有天然的无后效性。是否存在明显的“大者优先”或“小者优先”的倾向比如时间最早结束、区间最靠左、价值最高、跨度最大、范围最远。一旦你发现某个“排名属性”越极端越好那大概率就是在暗示贪心策略。这三重门不是严谨数学证明但它们是判断方向的雷达。真正的考场或面试场景里你没有时间做严格反证先用这三条快速判断再找一两个反例尝试推翻自己这是最稳妥的实战打法。3. 经典题型拆解从“看懂答案”到“自己能想到”下面进入真正的主角几道力扣上训练价值极高的经典贪心题。我选的这几道覆盖了最核心的贪心模型——排序双指针、区间覆盖、边界维护、贪心构造。每一道我都会按“为什么想到贪心 → 贪心策略是什么 → 为什么正确 → 代码实现 → 复杂度与变式”的顺序拆完看完了你就能明显感觉到贪心题目其实是有肌肉记忆的。3.1 分发饼干最简单的排序双指针贪心用来建立信心题目背景是用饼干喂孩子每个孩子有胃口值 g每块饼干有尺寸 s一块饼干只能分给一个胃口不超过它的孩子问最多能喂饱几个孩子。这是一道基础的入门题但它把一个非常重要的贪心模型完整地展现给了你两端排序后双指针同时移动。为什么想到贪心因为这里明显存在一个“能喂就喂”的倾向——如果最小的饼干喂不饱最饿的孩子那它留着也喂不饱更饿的所以不如尽量用最小的饼干去满足当前能喂的孩子。注意这里有两种表面上看都合理的策略大饼干喂大胃口和大饼干喂小胃口。前者是“我尽量满足难满足的孩子”后者是“我尽量让每块饼干都不浪费”。到底哪个对我直接说结论大饼干优先满足胃口大的孩子才是最优策略。理由是这样的如果一块大饼干喂了一个小胃口的孩子那大胃口的那个孩子可能就再也找不到合适的饼干了而小饼干通常喂不饱大胃口的孩子。反过来大饼干喂大胃口小饼干喂小胃口两边都能发挥作用。这是一个很经典的“资源错配”教训贪婪不是盲目抢最大而是要把合适的资源放在最需要它的地方。def findContentChildren(g: list[int], s: list[int]) - int: g.sort() s.sort() i j 0 while i len(g) and j len(s): if s[j] g[i]: i 1 # 孩子 i 被满足移动孩子指针 j 1 # 无论是否满足饼干都被消耗 return i代码极其简单但请你注意一个细节为什么孩子指针只在满足时移动而饼干指针永远移动因为排序后如果当前饼干喂不饱当前孩子那后面的孩子胃口更大这块饼干肯定也喂不饱任何人只能丢弃。这就是贪心策略能保证不亏的核心——要么喂饱一个需要最小饼干的孩子要么确认这块饼干没有价值。这道题变式很多比如“每个孩子最多分两块饼干”“饼干可以掰开”等但核心永远是排序后找匹配。它是贪心里最基础的双指针模型是后面几乎所有区间、配对类题目的雏形。3.2 跳跃游戏每次不要跳最远而是维护“可达区间”如果说分发饼干是排序贪心的入门那“跳跃游戏”系列就是“区间维护式贪心”的经典代表也是我面试别人时最爱用的题目之一因为这道题完美地测试候选人对“局部最优”的理解深度。题目描述很简单给你一个数组 nums每个元素表示你在该位置最多能往后跳多远初始位置在下标 0问你能否跳到最后。许多人第一次做这道题时会很自然地想“那我每次都跳最远的距离不就完了”这个直觉是错的。为什么错因为你当前位置能跳的最远距离不代表你应该立刻跳到那里去。举个反例nums [3, 2, 1, 0, 4]在 0 号位置最远能跳到 3但 3 号位置恰好是 0后面全是死路。如果你跳到了 2 号位最远也只能到 3同样死。正确思路不是“跳最远”而是维护一个当前能到达的最远右边界然后不断用范围内的新点去延长这个右边界。这是一个区间覆盖的思想你所能到达的每一个位置都会展开一个新的子区间只要最右边界还在推进你就有机会达到目标一旦某个点无法再推进右边界而目标仍不可达就宣告失败。def canJump(nums: list[int]) - bool: reach 0 for i, step in enumerate(nums): if i reach: return False # 到达不了 i 这个位置更别说到终点了 reach max(reach, i step) return reach len(nums) - 1这个代码为什么是贪心因为它每一步都是在当前能到达的范围内选择能让“最远可达位置”扩得最远的下一步。循环过程中reach 代表的不是某一次跳多远而是整个已探索区域的边界。每一步的局部最优决策取最大 reach直接服务于全局目标而且不会有后顾之忧因为范围内的每个位置都已经被自然覆盖你不需要去管具体在哪个位置落脚。这道题的变式非常多跳跃游戏 II 要求最少跳跃次数跳跃游戏 III 是 BFS/DFS 的图搜题进阶版甚至可以配合线段树。但核心的“区间推进”思想一旦建立起来后面都会顺理成章。刷熟悉这一题后你会发现自己对“覆盖”“边界”“推进”这三个词的敏感度大幅提高这对接下来的贪心进阶很有帮助。3.3 加油站寻找合法起点需要一点数学直觉接下来这道题是最容易让初学者怀疑人生的“加油站”题目。两个数组 gas 和 cost分别表示每个加油站的油量和到达下一个站消耗的油量车的油箱初始为空请你找到一个起点下标使得从它出发能环绕一圈回到起点若无解返回 -1。暴力做法很简单把每个下标当起点模拟一圈复杂度 O(n²)。但题目要求 O(n) 内解决。而它的贪心解法还有一个非常“反直觉”的现象为什么从某个点失败之后可以跳过它和它之前的所有点直接以下一个点作为新起点我先说正确答案把 gas[i] - cost[i] 统计成 diff[i]从 0 开始累加如果累加和在某一步小于 0就说明从当前记录的起点出发不能通过这一步那么把起点更新为 i 1同时清零累加和重新开始。最后如果总余量非负则最后一次重置的起点就是答案。这个策略的依据其实是一个数学事实如果从 A 点出发出现负油量失败在 B 点那么从 A 到 B 之间的任何一点 C 出发也同样会在 B 点或更早失败。为什么因为从 A 到 C 的过程中油箱剩余量是非负的如果中途为负早就失败了这意味着你带着“正的初始存量”到达 C 都到不了 B那么从 C 出发相当于初始为 0就更不可能通过 B 了。这个推理是朴素但典型的“反证法式贪心证明”你应该在做题时养成这种推导习惯。def canCompleteCircuit(gas: list[int], cost: list[int]) - int: total 0 # 全程总剩余油量 current 0 # 当前起点下的剩余油量 start 0 for i in range(len(gas)): total gas[i] - cost[i] current gas[i] - cost[i] if current 0: start i 1 current 0 return start if total 0 else -1代码只有十行但你能感受到它的“跳跃式思维”一旦 current 变负直接把起点挪到失败位置的下一站这一步不仅没做回溯反而跳过了大量无效枚举。很多人第一次看这个解法时都会怀疑它是不是碰巧对了但经过上面的反证你就会明白失败点之前的任何起点都是被同一个失败点同时否定的所以没必要再试。这种“失败后大跨度跳跃”的模型在贪心题里是一个非常重要的思想当一次尝试失败时往往可以一次性淘汰掉一整个候选区间而不是只淘汰当前这个候选。3.4 区间问题三件套无重叠区间、用最少的箭引爆气球接下来是贪心里最奢侈的一类“区间调度问题”也是面试中出现频率最高的一类贪心题之一。典型代表是“无重叠区间”和“用最少的箭引爆气球”。它们的共同点是给你一堆区间让你做一些删减或合并目标是让结果最优。“无重叠区间”题意是给定一个区间的集合请你计算需要移除的区间数量使得剩下的区间互不重叠。解法是一个经典的贪心模板将所有区间按右端点排序然后维护一个当前已选区间的右边界 end遍历时如果当前区间的左端点 end就保留它并更新 end否则这个区间必须被移除计数加一。为什么按右端点而不是左端点这是这道题最关键的思考点。按区间的右端点排序每次取“结束最早”的区间能最大限度地给后面的区间留下空间这是标准的“最早的结束时间优先”策略。如果你按左端点排序会出现一种情况一个区间左端点很小但右端点非常靠后选中它之后把后续所有区间都挡住了这种决策显然是次优的。所以“最早结束”才是贪心收益最大的方向这个思想在任务调度、会议室安排里都一样甚至可以推广到现实的排课表问题。def eraseOverlapIntervals(intervals: list[list[int]]) - int: intervals.sort(keylambda x: x[1]) end float(-inf) cnt 0 for l, r in intervals: if l end: end r else: cnt 1 return cnt“用最少的箭引爆气球”则是在此基础上增加了一层处理。它的题意可以理解成所有气球的横向直径是一个区间箭从某个 x 坐标垂直射出只要 x 落在气球区间内就能引爆它问最少需要几支箭。这个题看起来和无重叠区间不一样但本质上也是一个“区间重叠最大化”的问题你希望一支箭能引爆尽量多的气球相当于寻找最多重叠的区间集合。我的做法是先按右端点排序然后遍历区间用当前箭的引爆位置初始为最小右边界去尝试引爆后续气球。下一个气球如果左端点大于当前箭位置说明之前那支箭戳不破它必须新开一支箭同时更新引爆位置为当前气球的右端点。代码几乎就是无重叠区间的镜像版本。把这两个题放在一起练你就能建立“右端点排序→维护右边界→线性扫描”这一整套区间贪心的肌肉记忆这是面试时一个非常有辨识度的套路。4. 贪心与动态规划的分界线什么时候必须“有后见之明”4.1 无后效性贪心能解的题往往不“记仇”有一个概念你必须从早期就建立清楚贪心之所以能奏效是因为它面对的问题状态具备“无后效性”或者叫“无后向性”。翻译成人话就是你做的每一步决策只影响未来的状态而不需要回顾或修改过去的状态。过去的决策已经锁死而且不会因为后续的发展而被证明是错的不需要“翻案”。反过来一旦题目允许“之前的选择可以因为之后的信息而被推翻”贪心就失效了你需要动态规划来保存多种可能的中间状态。举例来说“最大子数组和”——经典动态规划里用到 Kadane 算法的题从表面看它也是每一步取当前最大但它的正确性依赖保存“以当前位置结尾的最大和”这个状态严格来说它是在做动态规划的状态压缩而不是纯贪心。类似地“0/1 背包”“最长递增子序列”这类题目每一步的决策都需要回顾历史贪心无能为力。我建议你用一个非常硬核的判据来分割贪心和动态规划如果问题的候选空间里存在多个互斥的中间状态并且你不知道哪个状态最终最优那就不能贪心因为贪心只保留“当前的一个最优状态”。动态规划保留一张状态表通过递推逐步覆盖所有候选路径。在这个意义上可以粗暴地理解为贪心是一维的 DP动态规划是多维的 DP。这不是严谨定义但做题时非常实用。4.2 零钱兑换的贪心陷阱与 DP 的必要性前面我提过 1、5、11 面额凑 15 的反例。这里再展开一点。如果你把每个面额理解为“背包里的物品”目标金额理解为“背包容量”那么硬币之间会产生非常复杂的替代关系少用一张大面额可能需要多张中面额多用了大面额剩余空间可能无法被小面额整除。这种“牵一发而动全身”的特性直接击穿了贪心的“局部最优不翻旧账”的假设。当你在面试或刷题中遇到这种“看起来像贪心但给不出严格证明”的题最好的策略是用一个反例快速推翻自己零钱兑换就是教科书级别的反例。有意思的是如果面额设计成人民币的 1、5、10、20、50、100贪心恰好又是正确的因为这是一个“规范货币系统”。所以做题时你可以尝试用贪心写一版再用动态规划写一版对比一下在什么情况下贪心会出问题这比纯背结论更透彻。我给一个“直觉优先级”建议看到题目先评估是否满足 2.2 的三重门满足则优先尝试贪心因为编码和调试成本低不满足或反例易举转头就上动态规划、记忆化搜索或回溯。刷题阶段两种方法都实现一遍会大大加深你对“状态设计”的理解能力。4.3 典型场景速查哪些标题一读就高概率是贪心还是 DP这里给一个速查风格的经验表来自我刷题过程中的主观统计不是理论定律但很实用题目特征大概率思路最小/最大化“数量”“次数”“区间数”且可以先排序贪心 排序需要输出具体操作序列且每一步只消耗一个元素贪心优先队列辅助组合优化且需要“考虑之前所有选择的影响”动态规划 (背包、LIS、编辑距离)树上路径、计数类、棋盘类包含多种转移方向DFS / 动态规划 / 回溯求“是否可行”且决策可以在线覆盖贪心区间覆盖式求“所有可行方案”或“字典序最小路径”且难以贪心回溯 / 状态搜索这个表的核心逻辑是题目如果允许你把问题的每一步拆成“只针对剩余部分”的独立子问题并且你可以找到一个不需要回看的排序优先级那它就是贪心的主场。5. 实战避坑与面试表达那些写代码前容易掉进去的深坑5.1 贪心题的高频翻车现场在我带过的新人和自己反复做题的过程中贪心题最容易翻车的点我总结成下面几个高频率场景你务必对照着自查一是没有证明就敢写。这里的“敢写”分两种一种是直接开写全凭直觉和样例另一种是虽然先想了反例但反例找得不好被一个弱样例骗了。我的建议是写代码前至少花 30 秒在草稿上尝试构造一个反例。如果构造不出来再写代码。这样做看上去慢了但长期来看会大幅提高你的正确率和“一次过”的感觉。二是排序规则没想清楚。区间题按左端点还是右端点排序字段对结果影响巨大。我之前分享过无重叠区间为什么按右端点排这类“决定性细节”不能靠记要靠理解。常见的还有“合并区间”要按左端点排序“会议室 II”在扫描线里则要让事件排序顺序反了逻辑会立刻崩。三是在需要优先队列的场景里硬用排序。有一些贪心题比如“最多会议数量”“IPO 项目收益”每做完一个任务可用选择集合会动态更新单纯排序不够需要用小顶堆或大顶堆动态维护。这种题如果你用“排序后从头到尾扫描”的思路大概率会遗漏“后面新解锁的更优选项”。请在思维里把“排序”和“优先队列”都看作贪心的辅助工具两者配合才是完整打法。四是忽略边界条件。下标 0 的位置、空数组、数组元素全相等、区间为闭区间还是开区间这些在贪心题里最容易出 bug。比如跳跃游戏里 reach 初始为 0 时如果数组长度为 1循环不进入但答案应该是 True这需要特判或调整循环逻辑。五是把“局部最优”直接等同于“每一步最大/最小”。这个错误我在跳跃游戏里已经详细剖析过最忌讳的就是看到“最多跳多远”就直接跳最远。请始终记住贪心的“最优”是站在全局目标下的局部最优往往体现为边界的最优扩展而不是动作幅度的最大表现。5.2 面试时如何讲清你的贪心思路加分的表达结构如果你在准备算法工程师面试那么除了把题目做对还要能把思路讲得像一个严谨的工程师而不是一个碰巧猜对答案的选手。我强烈建议你在描述贪心解法时按这个顺序组织语言先说目标我要最小化/最大化什么用一句话定义清楚。再说排序/选择规则我基于哪个属性做排序每次按什么规则选择一个候选。这里最好给出选择规则的“直觉理由”例如“结束越早留给后面的空间越大”。关键论证证明“一旦选择了当前最优不会影响剩余子问题的最优解”。你可以用反证法假设全局最优解不包含当前贪心选择将它替换为贪心选择结果不会变差——这推翻了假设所以贪心选择必然属于某个最优解。最后实现要点说一下时间复杂度、空间复杂度以及你如何维护关键边界条件。这三板斧说下来即使在面试官面前没能立刻想到正确解法你分析问题的框架也会让面评好不少。很多候选人算法能力不弱但输了表达这点一定要重视。5.3 一套实用的贪心刷题顺序按难度渐进推进最后给一份我筛选过的进阶路线涵盖力扣LeetCode上最经典的贪心真题按难度从入门到进阶排列跟着刷完会有非常立体的体感入门单循环贪心455 分发饼干、1005 K 次取反后最大化的数组和、860 柠檬水找零、135 分发糖果区间贪心435 无重叠区间、452 用最少数量的箭引爆气球、56 合并区间、763 划分字母区间覆盖与跳跃55 跳跃游戏、45 跳跃游戏 II、1024 视频拼接、134 加油站动手构造与双堆贪心621 任务调度器、767 重构字符串、871 最低加油次数、502 IPO综合贪心 / 困难题630 课程表 III、1353 最多可以参加的会议数目、605 种花问题、2099 找到和最大的长度为 K 的子序列这套路线的设计思路是先用单循环建立“每一步选最佳”的直觉再用区间题加深“排序属性选择”的判断力接着用跳跃、加油站这类“区间覆盖 失败后跳过”的题型训练模型迁移能力最后用优先队列辅助的动态贪心题把难度拉起来。每一层都是在上一层基础上加的不会让你直接摸到天花板。提示一下贪心的题目变式极多但核心套路并没有“几十种”那么夸张真正高频的模型就是排序贪心、区间贪心、堆贪心、计数贪心、数学贪心这几类。建议每刷完一个模型就做一次三到五题的“同模型复现”体会不同题面下的同一骨骼比盲目追求题数要高效得多。6. 一把最后的钥匙这篇文章从贪心的数学根基讲到了高频题型再从动态规划的边界讲到面试表达核心只围绕一句话贪心不是“每一步做最大”而是“每一步做最不亏”。当你真正开始用“反例思维”和“子问题独立思维”去审视每一道题贪心就不再玄学而是一把极其锋利的刀。我个人刷贪心题最大的体会是它的门槛不在代码能力而在“责任判断”——你要为一个还没发生的全局结果选择一个不可回头的局部决策这种勇气必须靠大量证明练习来支撑。所以建议你在刷题笔记里为每道贪心题固定写上一两句话的“为什么贪心正确”久而久之你会发现自己对题目的判断速度会明显快于那些只刷不做总结的人。如果你在刷题过程中碰到一道“看起来可以贪但总担心哪里不对”的题欢迎带着你的思路和反例去复盘体系里多走几轮这往往是最涨功力的时候。这一讲主要覆盖了贪心的基础模型和经典题目后续我们会继续往堆贪心、区间覆盖变式与贪心结合二分的方向深入把更复杂的拖累场景也一并拿下。