1. 贪心策略最直观也最容易被反杀的算法思想说实话每次有朋友问我算法该从哪里入门我给出的建议里永远有一个固定的选项把贪心算法吃透。不是因为贪心最简单——恰恰相反贪心的代码通常短到让人怀疑人生但它背后的证明和边界判断才是真正劝退大多数人的地方。贪心算法Greedy Algorithm的核心主张就一句话在每一步决策时只选择当前看起来最优的方案并且绝不回头调整。这个思路特别像你在自助餐厅取菜——先夹一眼看过去最想吃的吃完再说至于后面会不会出现更想吃的那不是当前要考虑的事。这种“走一步看一步、选完不后悔”的策略天然适合处理一类具备特定数学结构的问题局部最优能够递推出全局最优。换句话说每一步的选择都会让当前状态变得更好而最终所有“更好”累加起来恰好就是全局最优解。那它能解决什么问题几个典型场景你肯定不陌生任务调度给定一堆带截止时间和收益的任务怎么排能拿到最大收益区间问题有一堆会议时间段怎么安排才能参加最多的会议哈夫曼编码构造最优前缀编码让压缩后的总长度最短。最小生成树Prim、Kruskal 这两个经典算法本质都是贪心的变体。适合谁来学我觉得有三类人最该看。第一类是准备面试的求职者面试里贪心考得不算少而且题目特征明显学会了性价比极高第二类是刷 LeetCode 卡在“明明有思路但写不对”的初学者贪心能帮你建立“先证明再写码”的工程习惯第三类是工作中需要做资源分配、路径规划、排班策略的开发者这类业务问题里经常藏着贪心的影子只是没人告诉你而已。先说清楚一个最基本的认知贪心不等于“拍脑袋选最优”。一个合格的贪心方案背后一定存在严格的数学证明或至少是极其直观的逻辑支撑。判断一道题能不能用贪心思路其实比代码重要得多。2. 局部最优与全局最优贪心成立的底层前提2.1 贪心策略的数学基础贪心选择性质与最优子结构要搞懂贪心必须先搞懂两件事贪心选择性质和最优子结构。贪心选择性质每一步的局部最优选择最终可以组合成全局最优解。注意这不是侥幸它要求这个性质在数学上成立。最优子结构一个问题的最优解包含其子问题的最优解。也就是你把大问题切成小块每个小块单独求最优拼起来就是大问题的最优。这两者和动态规划的要求很像。区别在于动态规划会穷举所有子问题然后挑最优贪心只选当前看起来最好的那一条路走到底。你可以把动态规划想象成提前把地图上所有路线都走一遍再选最短的那条而贪心是每到一个路口凭眼前信息选一条最顺眼的继续走不再回头验证。也正因如此贪心的代码通常非常短。LeetCode 上一道中等难度的贪心题核心逻辑经常只有十几行。新手容易因此产生“贪心很简单”的错觉——代码短不等于容易真正的难点在于你得先说服自己这条路走到黑一定能得到最优解。2.2 一个决定性的判断准则贪心什么时候失效我见过太多初学者包括当年的我自己犯同一个错误拿到一道题感觉可以用贪心写了一版代码样例过了提交之后发现错了一半。为什么因为大部分“感觉可以贪心”的题目实际上贪心根本不成立。最经典的失效案例是零钱兑换问题假设有面值 1、3、4 的硬币要凑出总金额 6。如果贪心地每次选最大面值过程是先选 4再选 1再选 1总共 3 枚硬币。但实际上最优解是 3 3只用 2 枚硬币。这就是典型的局部最优先拿最大的导致全局不优硬币总数不是最少。所以在动笔写代码之前必须问自己三个问题每一步的最优选择是否只依赖于当前状态做了选择之后剩下的子问题是否完全独立于之前的选择如果反悔或回溯是否能找到比当前策略更好的结果如果答案是“能”说明贪心大概率不成立。我个人的习惯是先用直觉写一个贪心方案然后专门构造反例去攻击它。如果攻击了半个小时还没找到反例再考虑是不是该信它一回。这道工序省不得尤其在面试场景下面试官大概率会追着问你“凭什么贪心是对的”。2.3 分层理解贪心 vs 动态规划 vs 暴力搜索把三种思路放在一起对照才能看出贪心的“生态位”。我做了张表方便你对比着记维度贪心算法动态规划暴力搜索核心策略每步选局部最优枚举所有子问题并取最优枚举所有解空间时间复杂度通常最低O(n) 或 O(n log n)中等多项式级别最高指数级别需要证明正确性是必须依靠状态转移方程的严谨性天然正确不需要证明实现难度低中高低但空间爆炸适用条件贪心选择性质 最优子结构最优子结构 重叠子问题无限制代码量极短中等短但爆栈风险高从这个表可以看出来贪心是“赌性最强”的算法——它赌的是每一步都选最优最后一定全局最优。这看起来像是一个很任性、很冒险的策略但一旦问题结构满足条件它的效率和简洁度是其他算法完全无法比拟的。3. 核心实操四道经典题目带你把贪心刻进肌肉记忆3.1 准备工作贪心题的正确刷题姿势在开始刷具体的题之前我要先分享一套自己摸索了很久才定型的刷题方法论。贪心题最难的不是写代码而是判断“这题能不能贪”。那怎么训练这种判断力我的建议是不看题解先自己凭直觉写一版贪心方案然后疯狂构造反例来攻击它。攻击成功说明这题或许需要动态规划或者回溯攻击失败就有了一定信心。这个过程看起来笨实际上非常高效——它强迫你像面试官一样思考而不是像学生一样背答案。另外强烈建议你建一个文档把每道题目的“贪心策略”和“正确性证明思路”都写下来哪怕只有两三句话。比如“为什么这里要排序排序之后能保证什么性质”、“为什么选择当前最优不会影响后续最优”。写清楚这些才算真正吃透了一道题。3.2 题目一分发饼干——最典型的入门题题目描述假设你是一位很棒的家长想要给你的孩子们一些小饼干。每个孩子最多只能给一块饼干。对每个孩子 i有一个胃口值 g[i]这是能让孩子满足的最小饼干尺寸每块饼干 j有一个尺寸 s[j]。如果 s[j] g[i]可以将这个饼干分配给这个孩子孩子会得到满足。目标是尽可能满足越多数量的孩子并输出这个最大数值。贪心策略面对这一堆孩子的胃口和一堆饼干尺寸一眼就能看出这道题天生具备“选完就不再后悔”的结构。做法是先把两个数组分别从小到大排序然后用双指针去匹配。每次尝试用当前最小的饼干去喂当前胃口最小的孩子如果喂不饱说明这块饼干对后面的孩子也大概率喂不饱直接丢掉换下一块更大的饼干。这段逻辑实现起来很简洁class Solution: def findContentChildren(self, 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 j 1 else: j 1 return i正确性直觉为什么这样就能保证“喂饱最多孩子”关键在于排序之后越小的胃口越容易满足如果不优先满足他们他们也不会被更大的饼干额外“优待”反而是浪费了大饼干。优先满足小胃口相当于把大饼干留给后面可能存在的更大胃口这就保证了不会出现“大饼干喂小鸡小饼干饿死大鸡”的浪费。这种直觉就是贪心选择性质的具象化。这题要避开的一个坑有人会习惯性地从大饼干开始匹配大胃口。这个思路也能 AC但思考路径完全不同——那是在“避免浪费大饼干”而本题默认目标是“数量最大化”所以从小胃口入手更直观。建议两种写法都练一遍体会一下细微差别。3.3 题目二摆动序列——看清“趋势”才能找到贪心点题目描述如果连续数字之间的差严格地在正数和负数之间交替则数字序列称为摆动序列。第一个差如果存在的话可能是正数或负数。少于两个元素的序列也是摆动序列。给定一个整数数组 nums返回 nums 中作为摆动序列的最长子序列的长度子序列是通过从原始序列中删除一些也可以不删除元素来获得的剩下的元素保持原始顺序。这道题如果你用动态规划做状态转移方程写出来也还好但实现起来比贪心要繁琐得多。贪心解法非常优雅甚至不需要额外空间class Solution: def wiggleMaxLength(self, nums: List[int]) - int: n len(nums) if n 2: return n prev_diff nums[1] - nums[0] count 2 if prev_diff ! 0 else 1 for i in range(2, n): diff nums[i] - nums[i - 1] if (diff 0 and prev_diff 0) or (diff 0 and prev_diff 0): count 1 prev_diff diff return count贪心策略的核心相邻两个元素的差如果同号或为 0说明趋势没有变化中间的元素就是“冗余”的可以直接忽略。只有当差值的符号发生翻转时才会形成一个新的摆动“峰”或“谷”。所以这里的贪心体现在只在趋势变化处计数其他情况一律跳过。我当年第一次做这题的时候直觉上很疑惑为什么要用 prev_diff 0 和 prev_diff 0 这种带等号的写法直接 和 不行吗答案是等你处理差分 0 的时候就明白了。数组 [1, 2, 2, 3] 的 diff 序列是 [1, 0, 1]如果严格判断符号翻转它会把中间那个 0 当做一个新的趋势变化从而错误地增加计数。带等号的写法可以正确处理“持平之后重新上升/下降”的情况。这种细节就是所谓“题感”的来源——你不踩一次坑单纯看书永远也体会不到。3.4 题目三跳跃游戏——贪心可以不“落地”就完成检查题目描述给定一个非负整数数组 nums你最初位于数组的第一个下标。数组中的每个元素代表你在该位置可以跳跃的最大长度。判断你是否能够到达最后一个下标。这道题的贪心更上一层楼它不需要真正“跳”只需要维护一个当前能到达的最远位置。你站在下标 i能跳到的最远位置是 i nums[i]那么从 0 到 i nums[i] 之间的所有位置理论上都是可达的。我们不断更新这个最远边界最后只要检查这个边界是否覆盖到了数组末尾即可class Solution: def canJump(self, nums: List[int]) - bool: max_reach 0 n len(nums) for i in range(n): if i max_reach: return False max_reach max(max_reach, i nums[i]) if max_reach n - 1: return True return max_reach n - 1贪心策略的核心在遍历过程中能找到“更远可达位置”的位置就更新 max_reach不需要管中间到底怎么跳因为从之前可达的任意位置出发只要 max_reach 覆盖了当前位置 i那么位置 i 就是可以被“间接到达”的。如果某个时候 i 已经超过了 max_reach说明当前位置根本到不了后面也没戏了。这里有一个很多初学者都会踩的坑不要把 nums[i] 当成“必须跳这么多步”它是“最多跳这么多”。所以更新边界的时候用的是 i nums[i] 和原边界的较大值而不是直接等于 i nums[i]。如果你用了等于数组 [2, 0, 0] 这一来就判错了。**代码里为什么提前 return True**因为一旦 max_reach 覆盖到末尾后续元素根本不用看了。这是个很关键的剪枝优化它在极端情况比如第一个元素直接就是 10 万下能把 O(n) 的常数系数降得很低。3.5 题目四买卖股票的最佳时机 II——把直觉变成可证明的策略题目描述给定一个数组 prices它的第 i 个元素是给定股票第 i 天的价格。设计一个算法来计算你所能获取的最大利润。你可以尽可能地完成更多的交易多次买卖一支股票。注意你不能同时参与多笔交易必须在再次购买前出售掉之前的股票。这道题很多人第一次看到会懵股价有涨有跌我到底该什么时候买、什么时候卖其实藏着一个非常反直觉但无比优雅的贪心策略只要今天的价格比昨天高就在昨天买入、今天卖出如果今天比昨天低或者持平就什么都不做。换成代码就是class Solution: def maxProfit(self, prices: List[int]) - int: profit 0 for i in range(1, len(prices)): if prices[i] prices[i - 1]: profit prices[i] - prices[i - 1] return profit等等这不就是统计所有相邻上涨段的总和吗是的而且这正是“贪心”的精髓只要有利可图就立刻落袋不预测未来不做长线持仓。你也许会觉得这样频繁交易会不会错过“先跌后大涨”的机会不会因为一次大涨被拆成了很多个“小涨”的和计算结果完全一样。比如连续三天的价格是 1、3、7你一次买入卖出赚 6分两天买入卖出赚 2 4 6数值一模一样。这道题给的启示特别大有时候贪心解不需要复杂的状态机只需要抓住“增量都是正数”这个核心。所有上涨的差值之和就是最大利润。这个结论从数学上看极其简单但你能在十分钟内想明白并且自信地写出来吗想明白了说明你对贪心有感觉了。4. 贪心正确性的证明方法从“感觉对”到“确定对”4.1 交换论证法每一步偷换都绝不劣化很多刷题党会卡在“为什么这个贪心是对的”这个问题上尤其是面试被追问的时候。这里我给你一套最通用的证明利器交换论证法Exchange Argument。它的核心逻辑特别简单假设存在一个最优解如果它不是我们贪心算法产出的解那么我可以在保持解最优性的前提下把“贪心选择”一步步交换进去并且整个解不会变差。反复交换之后最优解就“变成”了贪心解。既然贪心解可以达到最优解的质量那贪心就是对的。举个具体例子。分发饼干那道题假设我们有一个最优分配方案其中某个孩子被分到了较大的饼干而某个胃口更小的孩子被分到了更小的饼干或者没分到。如果我现在“交换”一下把这个较大的饼干给那个胃口更小的孩子把小饼干给胃口更大的孩子会发生什么两种情况小胃口的孩子本来就能吃下小饼干换了大饼干依然能吃饱没问题大胃口的孩子如果吃不下小饼干那他原本分到的大饼干被换走了确实可能变差。但你注意题目要求是“满足的孩子数量最多”即使交换之后大胃口的孩子吃不饱了小胃口的孩子仍然吃得饱而且那块大饼干并没有被浪费——它喂饱了原本可能只能吃小饼干的孩子。所以孩子总数不会减少。这就是“交换不劣化”的直观证明。掌握了交换论证法你会发现很多贪心题的正确性证明套路都惊人的相似找反例之前先试交换交换之后解不变差贪心就稳了。4.2 贪心领先法每一步都不落后于“假想最优解”第二种证明思路叫贪心领先Greedy Stays Ahead比较贪心算法的中间状态和最优解的中间状态。如果每一步贪心产生的“局部最优”都优于或等于“假设最优解”对应那一步的状态那么到最后一步贪心得到的整体结果必然不会比最优解差。最典型的案例是会议室安排问题给定一堆会议的开始时间和结束时间怎么选才能参加最多的会议经典贪心策略是按会议结束时间排序每次都选结束时间最早且不与已选会议冲突的会议。怎么证明它正确用贪心领先法是这样想的假设最优解选择的第一场会议是 A贪心选择的第一场会议是 B。由于 B 是所有会议中结束时间最早的所以 B 的结束时间必然不晚于 A 的结束时间。那么用 B 替换 A后续可选的会议集合只会比原来更大——因为 B 结束得早给后续会议留出了更多时间。如此递推每替换一场贪心解都不会劣于最优解。到最后贪心解就是最优解。这个证明思路非常优美它几乎不需要任何复杂的数学公式只需要一个朴素的逻辑结束得早 给后面省时间 能塞下更多会议。4.3 真的证明不出来怎么办反证法和递归思考兜底当交换论证法和贪心领先法都“不太好使”的时候还有两条退路反证法和递归思考。反证法的思路是假设贪心解不是最优解那一定存在一个严格更优的解。把这个更优的解和贪心解放在一起比较找出第一个“分叉”的位置然后在那个位置附近构造矛盾。这个方法听起来玄乎但实际操作起来非常直观——你只需要问自己如果我在这个分叉点改成更优解的选择后面的局面会不会变得更差如果不会更差那贪心就是对的。递归思考则是把“当前一步最优”拆成“当前一步 剩余子问题”。如果当前这一步的贪心选择能够让剩下的子问题更容易被解决甚至子问题可以直接忽略那贪心就是不二之选。跳跃游戏那道题就能这么理解当前能跳得越远后面需要解决的问题就越小直到为零。这里必须坦白说一句笔试面试中绝大多数贪心题的“正确性”根本不需要你严格证明。面试官问“为什么贪心是对的”更多的是一种思维考察——看你能不能给出一个合理的论证过程而不是真的要求你写出形式化的数学证明。所以我建议你把这个证明技巧当作“说服自己”的工具而不是“应付面试”的模板。5. 常见问题与避坑技巧贪心题的错误模式合集5.1 贪心失败前的典型征兆我在陪跑学员刷题的过程中总结了几个“贪心快失败了”的征兆。如果你在自测时发现了这些现象赶紧停下来重新审题排序之后思路反而混乱。很多贪心题需要排序但排序之后贪心并不总是自然成立。比如背包问题里的“单位价值最大优先”策略在部分背包可以切割中成立在 0-1 背包中就完全不成立。排序只是工具排序之后你怎么用才是考验。样例过了但提交错了一片。这说明你的贪心大概率只对样例数据结构有效对真实数据的分布不具备一般性。此时最有效的操作不是继续调代码而是构造反例。必须“回退”才能得到更优解。如果你发现方案里有“撤销之前选择”的操作那基本上就不是贪心了至少不是纯粹的贪心而更像回溯或动态规划。5.2 经典反例一眼识破假贪心下面这些题都是著名的“贪心陷阱”我强烈建议你亲手做一遍感受一下“以为能贪、实际不能贪”的挫败感题目看似合理的贪心策略实际正确解法反例说明0-1 背包按单位价值从高到低装动态规划最后一点空间会因为不可分割而浪费零钱兑换某些币值优先选大面额动态规划1、3、4 凑 6贪心 411不如 33最长递增子序列遇到更小就替换动态规划/二分替换策略不能简单靠“每步取最小”完成跳跃游戏 II每次跳最远贪心但需要维护边界下一步最远点每次跳最远可能在局部浪费步数尤其是0-1 背包我曾见过无数人拿贪心去解然后被反例教做人。这类“假贪心”题是面试官最爱用来筛人的——他们不是想看你背了多少模板而是想看你有没有判断“能不能贪”的敏感度。5.3 调试贪心代码的 4 个实用技巧贪心代码虽短但调试起来一点不轻松。我总结出四个技巧帮你把调试成本降到最低第一打印关键状态。贪心算法的每一步决策都依赖当前状态所以你要在代码里同步打印“排序后的数组”“当前选择的元素”“更新后的边界/累计值”。尤其是跳跃游戏这类题目打印 max_reach 在每个下标的变化能清晰看到贪心“覆盖”的过程。第二小规模暴力对拍。这是我最推荐的杀器。写一个复杂度极高但绝对正确的暴力解法枚举所有子集/所有方案然后随机生成小规模测试数据把贪心解和暴力解逐一比对。一旦发现不一致就立刻得到了一个反例剩下的工作就是分析这个反例为什么能让贪心失效。对拍脚本我建议用 Python 写几行就能搞定。第三边界条件专项测试。贪心题的边界极其重要尤其是数组长度为 0、1、2 的情况以及所有元素相同、完全递增、完全递减的极端序列。这些情况往往能让错误的贪心瞬间现形。第四考虑数据溢出。跳跃游戏如果给的数值特别大i nums[i] 可能超出 int 范围记得用 long 类型。虽然这道题不至于但养成这个习惯能帮你避免一些隐蔽的运行时错误。5.4 面试实战贪心题的标准回答流程曾经有学员问我“面试官出贪心题我应该先说什么”我的建议是遵循下面这条回答路径它能让面试官感受到你的思维过程而不是背答案理解题意举例验证先把题目用自己的话复述一遍举一两个例子。提出贪心策略直接说“我的想法是每一步选择……理由是……”。证明贪心正确性用交换论证或贪心领先的思路说清楚为什么局部最优等于全局最优。这步是决胜点一定要给足细节。分析复杂度排序 O(n log n) 还是遍历 O(n)空间是 O(1) 还是 O(n)写代码 跑测试边写边解释跑几个测试用例确认正确。这套流程走完面试官很难挑出毛病。哪怕你的证明不够形式化只要逻辑自洽也会被认为有扎实的算法功底。6. 贪心的进阶方向与系列规划6.1 part01 之后从“裸贪心”走向“贪心 数据结构”贪心算法很少单独出现它经常和其他技巧组合在一起形成更高级的算法范式。已知的常见组合包括贪心 堆优先队列配合贪心比如“安排课程”类问题每次遇到冲突时弹掉收益最小的课程把更多时间留给以后。贪心 双指针很多数组类贪心题目都有双指针的痕迹比如上面的分发饼干、跳跃游戏。贪心 二分最长递增子序列就是一个典型它的 O(n log n) 解法本质上是贪心 二分插入位置。贪心 差分数组区间覆盖、区间合并类问题里常常见到。建议你学完了 part01 的内容后先别急着把贪心“翻篇”。花两周时间每天做 1~2 道中等难度的贪心题重点训练两种能力——识别题目的贪心特征以及构造反例的能力。这两项能力单独拿出来比会写 20 个模板更重要。6.2 用“思考框架”替代“题海战术”我在带学员的过程中发现真正让人成长的从来不是题量而是思考的质量。针对贪心这一块我建议你每做完一道题都写一套“三问笔记”这道题的贪心策略是什么一句话能说完吗如果用交换论证交换的是哪两个元素交换之后为什么不会变差如果我坚持用另一个策略比如“每次取最大”“每次取最小”会在哪个测试用例上失败这套笔记不用写得多工整哪怕只是几行零散的注释都能帮你快速建立起“同类题目的模式识别”。等刷过二三十道贪心题后你会发现很多题长得不一样但骨子里的贪心策略惊人相似——排序 双指针、维护边界、叠加上升差值大致就这三板斧。6.3 part02 预告当贪心遇到“区间”与“重叠”会变成什么样我们下一部分会专门深挖区间类问题。区间问题是贪心算法的重灾区——面试中出现的概率极高而且每道题看起来都很像解法却天差地别。比如“无重叠区间”要你移除最少区间让剩下的区间互不重叠“合并区间”要你把重叠区间合并成一个“插入区间”要在已排序的区间列表中插入新区间。同样是区间三者的贪心点完全不同一个排序的方向不对全盘皆输。我会在 part02 中把这几道题放在一起对比分析帮你彻底解决“区间题一团浆糊”的痛点。如果你在刷题中有什么疑问或者有想让我拆解的题目方向欢迎在评论区留言。我尽量选择最有代表性的问题在后续章节里展开。最后再分享一点个人心得我自己学贪心的时候最大的幻觉就是“太简单了我全懂了”。直到有一天面试官随手出了一道零钱兑换我自信满满地写下贪心代码然后被一句“6 3 3你的是 4 1 1”当场教育。从那以后我写任何贪心之前都会先问自己一句你能找到一个反例来推翻自己吗找不到才配写代码。这个习惯我建议你也养成。