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, i+nums[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大于等于总堆数但小于N+k的关系，答案会不会超过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或者日常新的竞赛题里，常有人发讨论帖说"这题贪心是不是可以过"，下面跟着一堆热心老哥贴出反例数据。这些数据比我凭空构造更省力，往往也是我对一道题理解加深最快的时刻。这个习惯坚持下来后，我发现自己在面对周赛压轴题时，分析贪心可行性的速度明显变快了。希望这个办法也能帮到你。
