1. 贪心算法的内核先搞懂局部最优怎么堆出全局最优刷LeetCode Hot 100刷到贪心这个专题时很多人的第一反应是这不就是找规律吗。确实贪心算法看起来不像动态规划那样有明确的状态转移方程也不像回溯那样有清晰的递归模板它更像是一种每一步都选当前看起来最好的最后希望全局也最好的直觉策略。但真正上手做题就会发现难点从来不是怎么贪而是为什么这里可以贪以及贪错了怎么办。先说清楚一个基本认知贪心算法不是万能的。它只适用于那些具有贪心选择性质和最优子结构的问题。翻译成人话就是两点第一局部最优的选择不会妨碍后面做出更好的选择第二整个问题的最优解可以由一系列局部最优解拼出来。如果一道题满足这两个条件那贪心往往是最高效的解法时间复杂度常常是排序O(nlogn)或者线性O(n)比动态规划少一个维度代码也短得多。如果题目不满足比如经典的背包问题那贪心就会给出错误答案必须老老实实去DP。Hot 100里的贪心题数量不算多但覆盖的面很全有区间调度类的无重叠区间、有跳跃类的跳跃游戏、跳跃游戏II、有买卖股票类的最佳买卖时机、有分配类的分发饼干、有单调栈思想辅助的接雨水虽然这题严格说是双指针/单调栈但贪心思想贯穿其中。把这些题吃透基本就能掌握贪心在面试中的出题套路。我在刷这些题时最大的感受是贪心算法的代码往往十行以内就写完了但真正值钱的是能写出来之前在草稿纸上画的那几幅图以及能说服自己的那几句证明。接下来我按题型拆解Hot 100中的贪心题每一类都聊透。2. Hot 100里的经典贪心题每类都拆开揉碎2.1 跳跃游戏维护一个最远可达位置就完事了吗跳跃游戏是Hot 100里考察贪心最典型的题原题是给你一个非负整数数组nums你从下标0出发nums[i]表示你在该位置最多能跳多远问能不能到达最后一个下标。很多人第一次做这题会陷入DFS或者BFS的思路想去模拟所有可能的跳跃路径但那样复杂度就爆炸了。贪心的做法非常简洁维护一个变量maxReach表示当前能到达的最远位置。遍历数组如果当前位置i已经超过了maxReach说明中间某个地方断了直接返回false否则用i nums[i]更新maxReach。如果maxReach能覆盖到最后一个下标返回true。关键是理解为什么这个贪心是安全的。假设当前位置i可达那么区间[i, inums[i]]内的所有位置都是可达的。我们不需要纠结具体跳到哪个位置因为跳得远永远不亏——能到达更远位置的选择一定比只能到达较近位置的选择覆盖范围更大。这就像手里有一张公交车票能坐到第10站那第5站在不在覆盖范围内在。既然覆盖了就不存在选远了反而错过中间某站的问题。这就是贪心选择性质的直观体现。这道题的变体是跳跃游戏II要求用最少步数跳到最后一个下标。核心思路变成了BFS的层序遍历思想在每一跳能到达的范围内探路记录下一跳能覆盖的最远距离当遍历到当前范围的边界时步数加一把范围更新为探到的最远距离。我建议这两题连着刷先做I理解可达性再做II理解步数如何用范围扩张来统计。2.2 买卖股票的最佳时机一天之差利润差距就在于买点买卖股票系列在Hot 100里有两道一道是最佳买卖时机只能买卖一次另一道是最佳买卖时机II可以买卖多次。第一道题其实不能算纯贪心标准的解法是用一次遍历维护历史最低价然后计算当前价卖出能赚多少取最大值。但它的思维方式和贪心非常接近在遍历过程中始终记录如果我在过去某天买入今天卖出收益最大是多少。这个历史最低价就是当前状态下的最优买点遍历过程中不断更新它本质上就是在做贪心的决策。第二道题才是真正的贪心经典。允许无限次买卖但你在同一天最多只能持有一支股票问最大利润。很多人第一反应是低买高卖跌了就卖涨了就买但这里有个细节如果明天继续涨你今天卖了不就亏了吗贪心的解法更绝只要今天的价格比昨天高就把这个差价计入利润。也就是说把每一段上涨的坡度都吃到下跌的区间直接跳过。这个做法可能反直觉——它允许你在同一天既是卖出又是买入但题目确实没禁止这一点。更重要的是它正是局部最优叠加出全局最优的典型例子每一段正收益都收下所有正收益之和就是最大利润。证明也不难总利润等于所有卖出价减去买入价的累加任何一次交易都可以拆成相邻两天的差值之和把所有正差累加就是上界而这个上界是可达的。2.3 分发饼干排序后双指针喂饱更多孩子的最简策略分发饼干是贪心入门题中的入门题但越简单的题越能检验你对贪心选择性质的理解。题目给一堆饼干尺寸和一个孩子的胃口值每个孩子最多给一块饼干问能喂饱多少个孩子。贪心策略是先把饼干尺寸和胃口值都排序然后小饼干优先喂小胃口的孩子如果当前最小饼干满足不了当前最小胃口这个饼干直接废弃孩子需求升序所以如果最饿的孩子都喂不饱这块饼干就不可能喂饱任何后面的孩子。这个策略的直觉是资源不浪费。你手里有一块小饼干与其拿它去碰大胃口孩子然后被拒绝不如先试最小胃口的孩子。排序保证了之后每次拿出的饼干是当前最小的每次面对的孩子是当前最容易被满足的。每一步都把当前能确定的事情做到最优剩下的子问题又是一个同样结构的更小问题。这个减而治之的过程就是贪心算法在区间分配类问题中的标准打法。类似的套路在无重叠区间那题里也有但那个题需要按区间右端点排序而不是左端点原因是选右端点越小的区间留给后面的空间越大——这也是区间调度里非常经典的思想。2.4 爱吃香蕉的狒狒被问爆的二分贪心验证组合题Hot 100里有一道很多人一看标题就想笑的题叫爱吃香蕉的狒狒原题编号875其实应该叫Koko Eating Bananas。这题表面上不是贪心但它的判断函数里埋着贪心的逻辑。题目是狒狒有N堆香蕉每堆有piles[i]根它每小时能吃k根如果一堆不足k根吃完这堆后这一小时剩余时间不再吃要在H小时内吃完求最小的k。这题的核心是用二分法枚举k然后写一个check(k)函数判断是否能在H小时内吃完。check函数里怎么算时间呢对每一堆需要的小时数是(piles[i] k - 1) / k也就是向上取整。这一步为什么和贪心有关因为每小时只吃一堆、吃不完的剩下的时间不吃了这个约束意味着最优策略就是每堆都尽快吃完贪心地不浪费任何咀嚼能力在当前堆的剩余部分上。这个二分套验证的模式在算法题里很常见——外层二分答案内层贪心验证整个套路要熟练。很多人写这题时容易踩一个坑二分边界。左边界应该是1还是0呢必须是1因为k为0没有意义。右边界设为max(piles)就够了吗其实够的因为k取到最大堆的根数时每一堆一小时就能吃完总时间等于堆数N如果N H那这个右边界一定可行。还有些人会纠结如果H大于等于总堆数但小于Nk的关系答案会不会超过max(piles)不会的这个上界天然成立因为k取max(piles)一定能满足任何H N的情况而题目保证H至少是N不然永远吃不完。这类边界问题做多了就有肌肉记忆但第一次刷的时候值得停下来想清楚。3. 贪心算法的正确性证明别只会猜3.1 为什么你的贪心策略是对的交换论证法入门面试或者刷题时最怕的不是想不出贪心策略而是想出来之后心里没底不知道对不对。我在刷Hot 100贪心专题时养成了一个习惯每种策略都用一两种方法在草稿纸上验证一遍再写代码。这里分享最常用的两个证明工具。第一个是交换论证法。假设有一个最优解如果它和我们贪心得到的解不一样尝试交换最优解中相邻的两个选择使得它变得更接近贪心解同时不损害最优性。如果交换后总收益不下降说明贪心解至少和最优解一样好。经典的例题就是区间调度按结束时间最早选区间证明时假设最优解里第一个区间不是结束最早的把它换成结束最早的区间剩下的区间空间只会更大不会更糟。这个替换不损优的论证反复出现想通了以后很多题都能套。第二个是归纳法。对决策的步数做归纳每一步贪心选择之后剩下的问题规模和原问题相同只是变小了而且如果原问题有最优解那么贪心选择 剩余问题的最优解就能构成原问题的最优解。这要求问题具备最优子结构。什么是最优子结构简单说就是总问题最优则子问题也最优。比如跳跃游戏II假设我们从位置i跳到了位置j如果从j到终点有更优路径那整体就更优了矛盾。所以局部最远覆盖的贪心加上归纳就能证明整体最短步数。我说的这些证明方法刷题初期可以不完全严格化但至少要在脑子里跑通如果我不这么做换成别的答案会不会更好这个反证问题。常见的贪心翻车事故是每次拿两个数相加后放回求总开销最小——这题其实是哈夫曼树的套路要用堆维护最小值以及背包问题按单位价值排序贪心只能拿到分数背包的最优解0-1背包就会出错。Hot 100里出现的贪心题都避开了这种陷阱但你在周赛或扩展题里会遇到需要保持警惕。3.2 贪心和动态规划长得像但性格完全不同每次聊贪心算法都绕不开和动态规划的对比。这两者都依赖最优子结构但最关键的区别是动态规划会考虑所有子问题的解然后取最优贪心不会回头只按当前规则走一步算一步。用人话说DP是我看看所有的路哪条最顺再走贪心是眼下哪条路坡度最缓我就走哪条坚信后面也顺。在Hot 100中有些题两种方法都能做。比如买卖股票的最佳时机II用DP的状态机也能算定义两个状态分别表示当天持有和不持有的最大现金转移方程也简单。但贪心代码比DP短一半思路也更直接。再比如跳跃游戏也可以用DP从后往前判断可达性但这题贪心的O(n)明显更优。我个人的建议是面试中遇到这类题先评估题目约束里是否隐含了决策只会让状态范围扩大不会缩小或者收益可拆分等特征如果具备则优先尝试贪心写起来快、不容易错。拿不准的时候可以用几组随机小数据跑一遍暴力验证暴力BFS或DFS都能当裁判。这种暴力对拍的思路在刷题时非常实用我在后面会展开说。4. 常见问题与排查技巧实录这些坑我基本都踩过4.1 案例一跳跃游戏II里的什么时候才该跳一步跳跃游戏II这题我见过不少人卡在更新步数的时机上。错误的做法是每遍历一个位置就尝试更新答案导致步数统计混乱。正确的套路是维护三个变量当前步数能到达的范围curEnd下一步能到达的最远范围nextMax以及步数steps。遍历时不断更新nextMax当i到达curEnd时说明当前这一跳已经用尽必须跳一步steps然后把curEnd更新为nextMax。有一个非常隐蔽的边界问题是如果curEnd已经覆盖到最后一个下标还需要在i到达curEnd时强制steps吗不需要因为你已经可以到达终点了强制加步数会导致答案多1。解决的办法是在更新步数前判断一下curEnd是否大于等于nums.length - 1。这个细节就是典型的一测就错、一看就懂的边界问题。我在LeetCode评论区见过有人在这道题卡了一晚上就是因为在最后一个位置边界上多加了步数。遇到这类问题直接在草稿纸上走一遍短数组比如[2,3,1,1,4]把每一轮的curEnd和nextMax写出来一眼就能找到问题。4.2 案例二无重叠区间到底按右端点还是左端点排序无重叠区间这题Hot 100里有收录问的是移除多少区间能让剩下的区间互不重叠。主流解法是贪心求最大不重叠区间数然后用总数减去它。关键决策点在于排序规则。如果按左端点排序你需要从前往后扫并维护当前区间的右边界遇到重叠时保留右边界更小的那个区间因为右边界小给后续腾出的空间多。如果按右端点排序思路更顺畅每次选结束时间最早的区间加入结果然后跳过与其重叠的区间。我个人的经验是区间调度类的题默认先想按右端点排序。原因很简单结束得越早剩余空间越大这个直觉和证明都直接。按左端点排序也能做但它隐含着当两个区间冲突时必须保留右端点小的这个额外判断容易漏。Hot 100里还有一道合并区间那题反而必须按左端点排序注意区分合并区间要覆盖所有相关段所以从左往右扩张无重叠区间要保留最多互不干扰的段所以尽量早结束。这两题并排刷一遍你对排序方向背后是决策目标这句话会有很深的体会。4.3 案例三二分贪心组合题的二分边界问题汇总爱吃香蕉的狒狒这题以及类似的在D天内送达包裹其实是LeetCode 1011这类的题目不在Hot 100里但配套练习很合适都容易在边界判断上出错。我整理了一个自查清单写这类二分验证题之前逐条过一遍左边界取多少答案的下界是什么比如速度最小为1还是可能为0注意题目语义。右边界取多少上限是最大值还是最大值加某个偏移要根据验证函数的单调性判断。验证函数是返回bool还是返回具体值如果用这个速度所需天数是否小于等于H作为判断那么二分得到的是可行域的左端点。循环条件用left right和right mid配合还是用left right和left mid 1配合两种模板都行但不要混用否则会出现死循环或mid卡死。爱吃香蕉这题的check函数里写(pile mid - 1) / mid时我特别提醒自己用整数除法向上取整而不是Math.ceil((double)pile / mid)因为后者涉及浮点数运算在数据很大时可能有精度问题。虽然LeetCode一般不会卡你浮点精度但在面试中写整数运算更为稳妥。4.4 对拍测试为什么你该给自己写个暴力验证工具我刷贪心算法题的一个小习惯是每次写完成功AC的贪心解法后如果这题不是特别简单我会顺手写一个暴力解法DFS、回溯、全排列枚举作为对拍器用随机小数据测试两者结果是否一致。这个方法帮我抓出过至少三四个看起来对其实错的贪心方案。具体操作很简单写一个genRandomInput()随机生成小规模数据然后分别运行贪心解法和暴力解法比较结果。不等则打印输入数据、贪心结果和暴力结果。对于数组规模5到10的题目暴力枚举完全可行跑几千组数据也不过几秒。这个习惯在复习Hot 100时特别有用比如无重叠区间、买卖股票时机这些题暴力版本很容易写验证一次之后你对贪心答案的信任度会大幅提高。面试时如果面试官问你确定这一定是对的吗你还可以把这个验证过程两三句话讲给他听它展示出的严谨性通常会得到很好的印象。4.5 关于贪心算法的复杂度分析贪心算法的复杂度往往是所有解法里最优的这也是它在竞赛和面试中备受青睐的原因。Hot 100里的贪心题使用HashMap或数组统计后一次遍历的通常是O(n)需要排序的一般是O(nlogn)。比如跳跃游戏是O(n)、分发饼干是O(nlogn)主要来自排序、无重叠区间是O(nlogn)。空间复杂度基本在O(1)到O(n)之间如果用了辅助数组记录状态则可能会是O(n)。有一次我在面试中被问到这个贪心算法能不能做到On时间复杂度问题是买卖股票的最佳时机II。我说可以因为只需一次遍历连排序都不需要。然后面试官追问如果要求只能最多交易两次呢这就变成动态规划题了得用四个状态变量辅助计算。这种追问套路几乎每家都在用本质上是考察你能否识别问题约束变化后贪心策略是否仍然成立。记住约束变了算法思路完全可以变。这是面试中非常常见的压力测试平时刷题时要刻意总结每类题在增加约束后解法如何升级。5. 我的个人经验与后续扩展建议5.1 一个贪心失败的案例复盘希望你少走弯路想和大家分享一个我自己翻车的案例有一次刷Hot 100之外的一道题大意是给一个数组每一步可以跳任意距离消耗的代价等于跳跃距离的平方问跳到末尾的最小代价。我第一反应是用贪心每次跳得越远越好因为单次跳跃的开销增长速度是二次方所以一次跳到底肯定最省。写完之后AC了但后来我把数组改成某些特定排列时发现不对劲重新用动态规划验证才发现贪心只在所有正数情况下成立如果数组中间有零甚至负数权重的变体贪心立刻失效。复盘下来我得到两条教训。第一贪心算法很容易在特定测试集上看起来对但你要主动构造反例来攻击自己的方案。第二判断能不能贪心的可靠方法是能否找到一个反例让局部最优决策导致全局次优。如果构造不出来再放心用。这种攻击性思维在算法学习中是长期受益的。5.2 Hot 100贪心题刷题顺序与配套练手清单如果让我给一个刷题顺序我会建议这样安排先做分发饼干和买卖股票的最佳时机II这两道题代码短、思维直观适合建立贪心其实就是每一步选当前最优的体感。接着做跳跃游戏和跳跃游戏II体会范围覆盖和步数统计的边界细节。然后做无重叠区间和合并区间把排序方向对比着学。之后穿插做爱吃香蕉的狒狒这类二分贪心验证的组合题理解外层枚举和内层检查的协作模式。最后可以把接雨水也拎进来虽然它更常被归到双指针或单调栈但它的从两端收缩维护左右最高柱子思想里也有贪心的影子能帮你打通专题之间的墙壁。配套练手的话我推荐LeetCode官方题库里的贪心分类大约有四五十道题。不用全刷挑几个经典题任务调度器、划分字母区间、根据身高重建队列、加油站、用最少数量的箭引爆气球。这些题分布在各大公司的笔试里出现概率很高学完Hot 100的贪心专题后刷它们会非常顺畅。5.3 最后分享一个让我受益的小习惯每做完一道贪心题我都会在评论区或者题解里看看别人构造出来的反例哪怕我的代码AC了也照看不误并把这些反例整理进自己的笔记。LeetCode周赛430或者日常新的竞赛题里常有人发讨论帖说这题贪心是不是可以过下面跟着一堆热心老哥贴出反例数据。这些数据比我凭空构造更省力往往也是我对一道题理解加深最快的时刻。这个习惯坚持下来后我发现自己在面对周赛压轴题时分析贪心可行性的速度明显变快了。希望这个办法也能帮到你。