贪心算法的核心思维：从“局部最优”到“全局最优”的落地
你可能觉得贪心算法“简单”——不就是每步选最好的吗？但我见过太多人栽在这“简单”里。比如有个朋友面阿里时，遇到“买卖股票的最佳时机II”，题目说可以多次买卖，他想“低买高卖”，就写了个只要后一天比前一天高就卖的代码，结果面试官问“如果价格波动很大，比如[1,2,4,2,5,7]，你的策略能赚到最多吗”，他才发现自己只考虑了相邻两天，没意识到“可以连续持有”。这就是贪心算法的第一个坑：把“局部最优”等同于“眼前最优”，忽略了策略的连贯性。
其实贪心算法的本质，是找到一个“能让局部最优累积成全局最优”的策略。就像你玩拼图，不用先看完整图（那是动态规划的思路），而是每次选最容易拼的那块——但前提是你知道“哪块最容易”是对最终结果有帮助的。我 了三个判断贪心是否适用的“灵魂拷问”，你在面试时可以直接套用：
怎么判断一道题能不能用贪心？记住这3个问题
《算法导论》里有句话我特别认同：“贪心算法的正确性证明，往往比算法本身更重要”。去年我带团队做校招面试，有个候选人把“跳跃游戏”做出来了，但当我问“为什么每次跳最远的位置一定能到终点”，他说“感觉是对的”，最后没通过。后来我才知道他刷了题但没理解原理——这也是很多人学贪心的误区：只记套路，不练证明。
为了帮你避开这个坑，我整理了一个“贪心策略验证表”，你在刷题时可以照着填，练多了就能形成条件反射：
| 题目类型 | 贪心策略 | 验证方法 | 常见反例 |
|---|---|---|---|
| 区间问题（如合并区间） | 按区间起点/终点排序 | 反证法：假设存在更优解不按此排序，推出矛盾 | 区间交叉但不包含时，未排序会漏合并 |
| 资源分配（如分发饼干） | 排序后从小到大/从大到小匹配 | 数学归纳法：假设前k个分配最优，证明第k+1个也最优 | 不排序直接匹配，导致大资源浪费 |
| 路径选择（如跳跃游戏） | 记录当前能到达的最远距离 | 反证法：若存在更远的可达点未选，会导致当前最远距离变小 | 每次跳当前位置能到的最远，忽略中间点的更远距离 |
你可以把这个表存在手机里，刷题时对照着想，慢慢就会形成“贪心直觉”。我自己当年学贪心时，就是用这个方法，3周内把LeetCode上的贪心题刷了一遍，后来面字节后端时，遇到“任务调度”题，当场就用反证法证明了“优先排出现次数最多的任务”的正确性，面试官直接说“这题过了”。
面试高频贪心算法题实战：从基础到进阶的解题套路
光说理论太空泛，咱们直接上题。我从近3年阿里、腾讯、字节的后端面试题里，挑了4道最常考的，从基础到进阶，每道题都带你走“策略分析→代码实现→面试官追问”的全流程。你可以跟着练，重点看我标红的“避坑点”——这些都是我和同事们面试时真实踩过的雷。
基础必拿分题：贪心策略“一眼看穿”型
这类题的特点是策略明显，排序后就能做，但容易在细节上出错。
例题1：分发饼干（LeetCode 455）
题目
：每个孩子有胃口值g[i]，每个饼干有尺寸s[j]，饼干尺寸>=胃口值才能满足孩子。求最多能满足几个孩子？ 你的第一反应可能是：把大饼干分给大孩子，不浪费。这个思路没错，但实现时容易踩坑。
我之前带的实习生小王，第一次做这题时写了“先排序g和s，然后用双指针从后往前匹配”，代码看起来没问题，但当输入是g=[1,2], s=[1,1]时，他的代码返回1（正确），但当输入是g=[2,1], s=[1,2]时，他忘了先给g排序，结果返回0（错误）。避坑点1：一定要先排序两个数组，而且是从小到大还是从大到小，要看清“谁迁就谁”。
正确步骤应该是：
面试官可能追问
：“如果饼干可以掰碎分，策略会变吗？” 这时候就不是贪心了，因为饼干可以拆分，变成“总量是否足够”的问题——你看，面试官就爱用这种变种题考察你对贪心适用场景的理解。
例题2：买卖股票的最佳时机II（LeetCode 122）
题目
：可以多次买卖股票，求最大利润（每天只能买或卖一次，不能同时持有多股）。 你可能会想：低买高卖，找所有递增区间。但我见过有人写成“找每个波谷和波峰”，代码复杂还容易错。其实有个更简单的贪心策略：只要当天价格比前一天高，就把这部分利润加上。
比如价格[1,2,4,2,5,7]，按这个策略：(2-1)+(4-2)+(5-2)+(7-5)=1+2+3+2=8，和“1买7卖”的利润（6）比，反而多2——因为你抓住了所有小波动。避坑点2：不要纠结“哪天长哪天下”，直接累加所有正差价。
进阶易错题：贪心+边界处理的细节把控
这类题的策略不明显，需要结合场景分析，而且边界条件多，面试官最爱追问“如果输入是XXX，你的代码会怎样”。
例题3：跳跃游戏（LeetCode 55）
题目
：数组nums[i]表示你在位置i能跳的最大长度，判断能否跳到最后一个位置。 你的第一反应可能是：每次跳最远的位置。但怎么证明这个策略是对的？
我面腾讯时就被问过这个证明，当时我说：“假设存在一个位置k，用贪心策略跳不到，但存在其他策略能到。那么在到达k之前，贪心策略跳的位置一定比其他策略远，所以如果贪心到不了，其他策略更到不了。” 面试官点头了——这就是反证法的思路。
实现时要注意避坑点3：不要模拟跳跃过程，而是记录“当前能到达的最远距离”。比如nums = [3,2,1,0,4]，最远距离初始是0，遍历到i=0时，最远距离变成3；i=1时，最远距离还是3（2+1=3）；i=2时，3+1=4>3，更新为4；i=3时，0+3=33（数组长度-1=4），但i已经超过当前最远距离3，所以返回false。
代码关键
：遍历过程中，如果i超过当前最远距离，直接返回false；如果最远距离>=数组最后一个位置，返回true。
例题4：合并区间（LeetCode 56）
题目
：给出区间列表，合并所有重叠的区间。 策略：按区间起点排序，然后遍历合并。但我见过有人排序后，合并时只比较当前区间的end和下一个区间的start，忽略了“下一个区间可能被前一个区间完全包含”的情况。
比如输入[[1,4],[2,3]]，排序后是[[1,4],[2,3]]，第二个区间的start=2 <= 第一个区间的end=4，且end=3 <=4，所以应该合并成[1,4]。避坑点4：合并时要取当前合并区间的end和下一个区间end的最大值。
正确步骤：
为了帮你直观对比，我做了个贪心vs动态规划的效率表，你在面试时可以主动提，显得你考虑全面：
| 题目 | 贪心算法 | 动态规划 | 推荐方法 |
|---|---|---|---|
| 跳跃游戏 | 时间O(n)，空间O(1) | 时间O(n²)，空间O(n) | 贪心 |
| 买卖股票II | 时间O(n)，空间O(1) | 时间O(n)，空间O(n) | 贪心（更简洁） |
| 合并区间 | 时间O(nlogn)（排序），空间O(logn)（排序栈空间） | 不适用（无重叠子问题） | 贪心 |
面试官追问
：“如果区间是按end排序的，合并策略会变吗？” 这时候你就要调整思路：按end排序后，应该优先保留end小的区间，避免重叠——这就是策略的灵活性，也是贪心算法的魅力所在。
你现在可以拿出笔，试着做一下这4道题，重点写“策略证明”和“边界处理”的注释。如果某道题卡壳了，别着急看答案，先想想我前面说的“3个灵魂拷问”，可能你只是忽略了某个条件。
其实贪心算法就像你学开车，一开始觉得“什么时候踩油门、什么时候刹车”很复杂，但练多了就会形成肌肉记忆。我 你每天花30分钟，选1道贪心题，按“策略分析→证明→代码→优化”的流程走一遍，2周后你会发现，再遇到贪心题，你第一反应不是“我做过这题吗”，而是“这个策略能不能用反证法证明”。
如果你按这个方法练了，下次面试遇到贪心算法题，欢迎回来告诉我你有没有顺利拿下！
你刚开始接触贪心算法的时候，是不是总在纠结“这题到底能不能用贪心啊？”其实我当时也一样，后来 出三个小问题，你对着题目问一遍，基本就能有谱了。第一个是“前面选的路不影响后面怎么走吧？”——这就是“无后效性”，比如分饼干的时候，给第一个孩子分了小饼干，剩下的饼干和孩子的选择又不会变，这就行；要是题目说“每个孩子只能拿比上一个大的饼干”，那前面的选择就影响后面了，贪心可能就不合适。第二个问题是“全局最好的结果里，是不是一定藏着局部最好的？”——比如求最大利润，要是全局最大利润是好几天赚的，那每天赚点小钱肯定得包含在里面，这就是“最优子结构”。第三个最关键，“每次选眼前最好的，最后能不能堆出全局最好的？”这个可以试试反证法，比如你说“按区间起点排序合并”，那就假设“不按起点排序能合并得更好”，结果发现合并出来的区间更多，矛盾了，说明你这策略没问题。
弄明白能不能用贪心之后，另一个常问的就是“贪心和动态规划到底有啥不一样？”其实打个比方你就懂了：贪心就像你逛街买衣服，看到一件喜欢的、价格合适的就直接买了，不管后面有没有更划算的；动态规划呢，就是你先把整条街的店都逛一遍，记下来每家的款式和价格，最后挑最适合自己的。所以贪心是“走一步看一步”，每次只选当下最好的，不用记前面的选择；动态规划是“提前规划”，得把中间路过的店都记下来，万一后面有更好的呢？就像最长递增子序列，你得知道前面每个位置的最长序列是多少，才能算出后面的，这时候贪心就搞不定了，就得用动态规划。
面试官特别爱问的还有“为啥你这个贪心策略是对的？”之前我有个朋友就栽在这儿，明明代码写对了，被这么一问就支支吾吾。其实你可以分三步走：第一步先把你的策略说清楚，比如“我是按区间的起点从小到大排序，然后合并重叠的”；第二步用反证法试试，“要是不按起点排序，比如有个区间起点小但终点大，结果可能就漏合并了，那肯定不是最优解”；第三步再举个例子，“你看这个输入[[1,4],[2,3]]，按起点排序后合并成[1,4]，要是不排序可能就变成[[1,4],[2,3]]两个区间了，明显不对嘛”。要是反证法说不清楚，也可以说“这题有无后效性，而且每次选局部最好的，最后加起来就是全局最好的”，面试官一般也能接受。
至于怎么练贪心最有效，我当时的笨办法是“分类刷题+写注释”。你可以按场景分，比如区间问题、资源分配、路径选择，每种场景挑3-5道题集中刷。每道题不光写代码，还得在旁边写清楚“我为啥选这个策略”“边界条件要注意啥”，比如合并区间的时候，得写“合并时要取两个区间终点的最大值，不然可能漏包含”。我当时坚持了两周，每天晚上花40分钟，后来再看到贪心题，第一反应不是“我做过这题吗”，而是“这个策略能不能用反证法试试”。
还有人问“题目条件变了，贪心策略咋调整啊？”这种变种题其实最考验你对贪心本质的理解。比如“分发饼干”那题，要是题目说“饼干可以掰碎分给多个孩子”，这时候贪心就不行了，你得算所有饼干的总量够不够所有孩子的胃口总和，因为饼干能拆分，就不存在“哪个饼干给谁”的问题了。再比如“合并区间”，要是题目说“按区间终点排序”，那你就得优先保留终点小的区间，避免后面的区间跟它重叠，这时候排序方式变了，策略也得跟着变。记住，不管题目怎么变，核心都是找到新条件下的“局部最优”，再看看能不能堆成“全局最优”，实在不行就换思路，别硬套贪心。
常见问题解答（FAQ）
如何快速判断一道算法题是否适合用贪心算法？
可以通过“3个灵魂拷问”快速判断：①是否具有“无后效性”？即前面的选择不影响后续选项（如分发饼干时，给孩子分饼干后不影响剩余选择）；②是否存在“最优子结构”？即全局最优解一定包含局部最优解（如最大利润问题中，全局利润由局部利润累积）；③能否找到“贪心选择性质”？即每次选择局部最优能累积成全局最优（可用反证法或数学归纳法验证）。若三个条件满足，大概率可用贪心算法。
贪心算法和动态规划的核心区别是什么？
两者的核心区别在于“决策逻辑”和“适用场景”：贪心算法是“走一步看一步”，每次做局部最优选择，不依赖后续状态（无后效性），适用于策略明确且能累积全局最优的场景（如合并区间）；动态规划则是“全局规划”，需要记录中间状态，考虑所有可能的子问题（有后效性），适用于需枚举多种情况的场景（如最长递增子序列）。简单说，贪心是“选当下最好的”，动态规划是“选 可能最好的”。
面试时被问“为什么这个贪心策略是对的”，该怎么回答？
可分三步回答：①先明确贪心策略（如“按区间起点排序后合并”）；②用“反证法”验证：假设存在更优解不采用该策略，推出矛盾（如“若不按起点排序，可能出现区间交叉未合并，导致结果非最优”）；③结合题目场景举例：用具体输入验证策略有效性（如合并区间中，排序后能覆盖所有重叠情况）。若反证法复杂，可退而求其次说“通过题目特征观察，该策略能保证局部最优累积成全局最优，如无后效性和最优子结构”。
刷题时如何高效练习贪心算法？
推荐“分类刷题+策略 ”法：①按场景分类（如区间问题、资源分配、路径选择等），每种场景选3-5道题集中练习；②每道题按“策略分析→证明→代码→边界处理”四步走，重点写“策略证明”注释（如反证法思路）；③ “策略模板”（如区间问题排序方式、双指针用法），遇到同类题可直接套用；④每周复盘1次错题，记录“踩坑点”（如忽略排序、边界条件判断错误）。坚持2-3周，可形成贪心算法的“解题直觉”。
贪心算法的变种题（如题目条件变化）需要注意什么？
变种题的关键是“抓住策略核心逻辑，灵活调整细节”。例如：①资源可拆分时（如饼干可掰碎），贪心策略可能失效，需转为“总量判断”；②增加限制条件时（如区间需按end排序），需调整排序方式（优先保留end小的区间避免重叠）；③多目标优化时（如同时考虑时间和空间），需明确“优先级”（如任务调度中，优先处理出现次数多的任务）。遇到变种题，先回归贪心本质——找到新条件下的“局部最优”，再验证是否能累积全局最优。
