LeetCode Hot 100里的贪心算法题数量不多加起来也就十几道但每一道都是面试高频。我刷到贪心这一块的时候有个很直观的感受代码往往不超过十五行可一旦想不明白为什么这么做是对的就会陷入“这个贪心我见过、但下次换个包装我又不认识了”的恶性循环。所以这篇文章我不打算只贴题解而是把Hot 100里的贪心题按题型拆开从算法导论的两个核心性质讲起逐题给思路、代码和证明思路再聊一聊周赛和真实面试里怎么识别贪心、怎么避免踩坑。如果你正在准备算法面试或者已经刷完链表、二叉树想集中突破贪心这篇文章应该能帮你把“会做某道题”升级成“会判断一类题”。1. 贪心算法到底是什么从“短期最优”到“全局最优”1.1 算法导论的两个核心性质贪心选择与最优子结构很多人对贪心的理解停留在“每一步选当前最优”这个说法没错但容易让人误以为贪心靠的是直觉和运气。算法导论第16章用了整整一章讲贪心算法核心就落在两个性质上贪心选择性质和最优子结构。贪心选择性质说的是你可以通过一系列互不后悔的局部最优选择最终得到全局最优解最优子结构说的是一个问题的最优解里包含了子问题的最优解换句话说你不需要回头调整之前做过的选择后面每一步只需要在当前剩余问题上继续做局部最优。我用吃自助餐来类比每次只取当下最想吃的一盘取完之后不换回去最终得到的就是“对这次取餐顺序来说最满意的一套”。但这套逻辑能成立前提是“当前最想吃的”永远包含在某个全局最优方案里。贪心算法真正的难点就在这里——你必须验证这个前提验证不了局部最优就会把全局最优带偏。这两条性质不是孤立存在的。最优子结构是动态规划也需要的贪心比动态规划更苛刻的地方在于动态规划会枚举所有可能的子问题贪心却要求每一步都能确定性地减少问题规模而且这个减少方式恰好是全局最优的。所以贪心可以理解为动态规划的一种特化只不过这种特化一旦成立复杂度往往就能从多项式级别降到一个排序或者一趟扫描的级别。1.2 贪心 vs 动态规划什么时候能“偷懒”算法导论里有个经典例子非常能说明问题活动选择问题。给你一组活动每个有开始时间和结束时间活动之间不能重叠目标是选出尽可能多的活动。按结束时间从小到大排序每次选结束最早且与已选活动不冲突的那个这就是贪心。但如果给每个活动加一个权重目标改成“选出总权重最大的相容集合”贪心就立刻失效了必须用加权区间调度的动态规划。两个问题只差一个权重解法就从贪心跳到了动态规划。这个例子对我来说是理解贪心边界最好的入口。它说明贪心并不是“动态规划的弱化版”而是“满足特定结构时的最优解法”。当你看到一道最优化题先别急着上动态规划要问自己这个问题在每一步做完选择之后剩下的子问题是不是完全独立如果独立再想一想“当前最优是否一定不劣于其他选择”如果能证明贪心就比DP省太多代码和复杂度。判断一个题能不能贪心我常用一个土办法把候选策略写在纸上然后强行构造反例。如果怎么构造都构造不出来再想想能不能用交换论证法证明如果反例很容易构造出来那就老老实实回去写动态规划。这个土办法虽然朴素但它逼着你去理解问题的结构而不是背模板。2. LeetCode Hot 100里贪心考点分布三种典型题型2.1 高频题清单一眼看出考察方向我粗略数过Hot 100官方题单里的贪心题主要集中在三个方向上序列最优类、区间调度类、排序构造类。序列最优类里最典型的是55跳跃游戏、45跳跃游戏II、122买卖股票的最佳时机II、134加油站区间调度类有763划分字母区间、435无重叠区间、452用最少数量的箭引爆气球排序构造类则是406根据身高重建队列、455分发饼干、860柠檬水找零。这些题表面千差万别但底子都是同一个东西——每次做一个确定性的局部选择这个选择直接决定后续的剩余问题。题型代表题核心策略时间复杂度序列最优55、45、122、134维护可达边界、累加正向差分O(n)区间调度763、435、452按右端点排序、记录末次位置O(n log n)排序构造406、455、860先排序再按规则安排O(n log n)这张表自己会说话凡是能用贪心解决的Hot 100题要么依赖一个排序要么依赖一趟线性扫描几乎不会出现两层循环嵌套的暴力优化。原因是贪心的本质决定了你不需要回头比较所以复杂度天然就低。如果你看到一个题你的解法需要反复回退或者重新尝试那大概率不是贪心的用武之地。2.2 三步判断法如何快速决定“能不能贪心”我在面试和刷题时总结了一个三步判断法虽然不保证百分之百准确但帮我避掉了很多假贪心。第一步把候选的局部策略写出来找一个小例子手动走一遍看结果是否合理第二步认真尝试构造反例想想是否存在“局部最优导致全局更差”的情况如果能构造出来直接放弃贪心第三步如果构造不出反例尝试用交换论证法或者数学归纳法把正确性补齐补不上就继续存疑。贪心还有个常见判断依据叫无后效性做过的选择不会影响后面选择的可行性或者说影响是可控的、确定的。一旦发现后续选择需要根据前面的选择结果动态调整就要立刻警惕。比如跳跃游戏里你维护的“最远可达位置”是单调递增的前面的选择不会让后面的可达范围变小这就是典型的无后效性而零钱兑换里你前面用掉多少枚硬币会直接影响后面还能用多少这时候就要考虑动态规划了。这三个步骤加起来最多花五分钟。五分钟换来的是不踩坑我认为非常值。尤其是面试时你说“这道题我想用贪心原因是我构造不出反例而且局部选择不会影响后续”这一句话就能让面试官知道你不是在背题而是真的理解贪心的边界。3. 高频题逐题拆解思路、代码与边界3.1 股票类122买卖股票的最佳时机II122题的场景是给你一个价格数组可以多次买卖但任何时候最多持有一股求最大利润。很多人第一次看会觉得这是动态规划实际上它是最典型的贪心变体。核心思路极其简单只要今天的价格比昨天高就把这个价差计入利润把数组中所有正向相邻差值加起来就是答案。为什么敢这么算因为允许“今天卖、明天买”这种切分操作持有一股的限制并不会阻断你把一段连续上涨拆成若干段正差价。比如价格从1涨到4整体利润是3拆成每天的正差价111还是3如果中间有一天下跌差价是负数直接跳过它就行因为跳过下跌等于没有交易不会产生额外成本。这个转化不是模拟真实交易而是数学上的等价变换代码自然短。def maxProfit(prices): total 0 for i in range(1, len(prices)): if prices[i] prices[i - 1]: total prices[i] - prices[i - 1] return total要注意一个细节有些题解把判断条件写成max(0, prices[i] - prices[i-1])效果一样但我个人更喜欢显式判断因为面试时更好讲清楚“正向差价累加”的逻辑。另外这道题在Hot 100里通常被归到“数组/动态规划”分类下但它真正的思维核心是贪心的区间切分思想和121题只能买卖一次不一样。121需要维护历史最低点属于扫描维护最值不是纯贪心别把两题混着背。3.2 跳跃类55和45从“能不能到”到“最少几步”55跳跃游戏问的是从数组第一个位置出发每个位置记录你能往后跳的最大长度能不能跳到最后一个下标。贪心做法只维护一个变量reach表示当前能到达的最远下标遍历数组时如果当前位置i已经大于reach说明中间断了直接返回False否则不停更新reach max(reach, i nums[i])。遍历结束reach如果覆盖了最后一个下标就返回True。这个解法看起来简单到不像话但关键在于理解“可达范围是单调的”只要reach更新过前面的所有位置都已经被覆盖检查过不需要回头。所以一个变量就够连DP数组都不需要。def canJump(nums): reach 0 for i, jump_len in enumerate(nums): if i reach: return False reach max(reach, i jump_len) return True45跳跃游戏II把题目改成“最少跳几次能到最后一个下标”难度立刻上一个台阶。我一开始想用DP后来发现有个非常巧妙的贪心视角把每一次跳跃当成一层BFS当前层是你现在能到达的所有下标你在这一层里找出能抵达的最远下标作为下一层的边界当遍历指针i走到当前层边界时跳跃次数加1边界更新成下一层最远。这样每一步都“挑能跳最远的”次数自然最少。def jump(nums): n len(nums) if n 1: return 0 steps 0 cur_end 0 farthest 0 for i in range(n - 1): farthest max(farthest, i nums[i]) if i cur_end: steps 1 cur_end farthest if cur_end n - 1: break return steps代码里有两个边界细节要特别小心。一是循环范围是range(n - 1)而不是range(n)因为一旦到达最后一个下标就不需要再跳了二是cur_end的更新时机必须在i cur_end时才加步数否则会把同一层内的跳跃重复计数。我见过不少人在这个边界上翻车导致结果多出一跳。3.3 区间类763划分字母区间与435无重叠区间763划分字母区间是我非常喜欢的一道题因为它把贪心藏在了字符串里。题目要求把字符串划分成尽可能多的片段每个字母只能出现在一个片段里。解法分两步第一次遍历记录每个字符最后一次出现的下标第二次遍历维护当前片段的右边界每次取当前字符的最后位置来扩展边界当遍历指针i正好等于边界时说明这个片段可以闭合记录长度后重置起点。为什么“能闭合就闭合”是最优的因为闭合得越早片段就越短在满足“每个字母只出现在一个片段”的约束下片段数量就越多。这是一个非常直观的贪心选择局部上你让每个片段尽可能短全局上就得到最多片段数。交换论证法也可以证明把任意一个片段向后延长都不会让总数量变多。def partitionLabels(s): last {c: i for i, c in enumerate(s)} res [] start 0 end 0 for i, c in enumerate(s): end max(end, last[c]) if i end: res.append(end - start 1) start end 1 return res435无重叠区间则是区间排序贪心的代表。给定一组区间要求移除最少的区间使剩余区间不重叠。贪心策略是按右端点升序排序然后保留结束最早的区间跳过所有与它重叠的区间。这个策略的直觉很简单右端点越早结束留给后面区间的空间就越大。代码里用last_end记录当前保留区间的右端点一旦发现当前区间左端点小于last_end说明重叠计数加1否则更新last_end为当前区间的右端点。def eraseOverlapIntervals(intervals): if not intervals: return 0 intervals.sort(keylambda x: x[1]) last_end intervals[0][1] count 0 for i in range(1, len(intervals)): if intervals[i][0] last_end: count 1 else: last_end intervals[i][1] return count这里有个很容易被忽略的坑排序键选右端点而不是左端点。如果按左端点排序你保留的区间可能是“开始很早但结束很晚”的它会压掉一大片后续区间按右端点排序才能保证每次保留的都是“最容易不占空间”的。这一点在452用最少数量的箭引爆气球里也一样箭的题本质上就是统计不重叠区间的数量策略完全相同。3.4 入门构造类455分发饼干与860柠檬水找零455分发饼干是贪心里最友好的入门题。孩子的胃口数组g饼干尺寸数组s每个孩子最多给一块饼干饼干尺寸大于等于胃口就能满足问最多能满足几个孩子。贪心策略是把两个数组都排序然后从小到大匹配用尽可能小的饼干去满足胃口最小的孩子。这个策略好就好在“不浪费大饼干”因为大饼干留给后面的孩子机会更多。def findContentChildren(g, s): g.sort() s.sort() i 0 for cookie in s: if i len(g) and cookie g[i]: i 1 return i860柠檬水找零稍微有点脑筋急转弯的味道。顾客付5、10、20三种面额买5美元柠檬水你一开始没有零钱判断能否给每个顾客正确找零。贪心点在于找15美元时优先用10美元加5美元的组合而不是三张5美元因为5美元是最稀缺的通货要省着用。def lemonadeChange(bills): five ten 0 for bill in bills: if bill 5: five 1 elif bill 10: if five 0: return False five - 1 ten 1 else: if ten 0 and five 0: ten - 1 five - 1 elif five 3: five - 3 else: return False return True这类“模拟贪心”题代码都不难难的是你要想清楚为什么“优先用大面额”是安全的。它本质上是在保护稀缺资源和区间调度里“保留早结束的区间”是同一个思想——优先消耗那些“对后续限制更小”的选项。把这些题串起来就会发现贪心题并不是一堆孤立的脑筋急转弯而是几个核心思想的排列组合。4. 正确性证明、周赛变形与面试讲解技巧4.1 交换论证法给贪心证明打底很多刷题的人看到贪心题就直接写代码写完一提交发现过了就认为自己懂了。但面试时面试官大概率会追问一句“你为什么觉得这是对的”这时候如果你答不上来前面的代码再漂亮也会打折扣。我给自己的要求是Hot 100里的每道贪心题都要能说出一句证明思路最常用的就是交换论证法。交换论证法的步骤很固定假设贪心解G不是最优解取一个最优解O找到G和O第一个不同的决策点把O里这个位置的选择“交换”成G的选择证明交换之后O不会变差反复交换最后O就变成了G得出G也是最优解与假设矛盾。活动选择问题就是教科书级的例子贪心选了最早结束的活动a如果最优解第一个活动是b那么b的结束时间一定不晚于a因为你按结束时间排序后a是最早的把b换成a后面的活动依然都能安排下数量不变所以贪心选择不劣于任何最优解的第一选择。这个方法最优雅的地方在于它让你把“证明”变成一种机械化操作而不是靠灵感。你可以先用交换论证法在草稿纸上验证任何贪心策略验证通过再动手写代码。Hot 100里的股票差分、跳跃边界、区间右端点排序全部都能用交换论证法打通建议你至少把763和435两道的证明过程自己写一遍写完再遇到同类题会很踏实。4.2 周赛430式的包装题怎么把贪心从壳里剥出来很多人刷完Hot 100去做周赛会发现一个扎心的事实题面包装越花你越难认出它到底考什么。拿周赛430这一档的场次来说第三题第四题经常是“选择若干物品使某指标最大”“把数组分成若干段满足某限制”这类看起来像是贪心的题实际上确实有很多就是Hot 100经典题的变体只是穿了一层“必须成对”“必须连续”“必须满足高度差”的外壳。我的处理流程是先把题目的壳剥掉抽象成三个问题决策变量是什么选择之间是否互相影响是否存在一个自然的排序规则如果决策变量是一个个元素元素之间没有强耦合而且能找到一个排序规则让局部最优不劣于其他选择那大概率是贪心。最典型的变形方式有两种一种是把区间调度变成“你需要安排若干任务每个任务有截止时间”本质还是按右端点排序另一种是把股票差分变成“你只能持有最多k股”本质还是分段取正收益。周赛题还有一个常见迷惑项就是故意在数据范围上诱导你写动态规划。比如数组长度给到10的5次方动态规划O(n²)必然超时这时候贪心基本是唯一出路。反过来如果数据范围不大你要警惕这题可能故意让贪心失效需要动态规划。范围本身不会告诉你答案但能帮你快速筛掉一部分不合理的猜想。4.3 面试现场讲贪心的三句话和边界控制真实面试里贪心题比动态规划题更容易被追问因为代码太短面试官只能从你的思路和证明过程里判断你是不是真会。我习惯用三句话打头阵第一句“这道题我想用贪心策略是……”直接亮出方案第二句“我构造过反例比如……”主动展示你的怀疑过程第三句“这个策略的正确性可以用交换论证法/数学归纳法证明”把证明思路讲出来。代码实现阶段我最关注的是边界条件。贪心题代码短但边界错一个字符就可能前功尽弃跳跃游戏里的i reach条件、跳跃游戏II里的range(n - 1)、无重叠区间排序后的空数组判断、柠檬水找零里5美元计数器归零的判断都是高频翻车点。写完后我会手动跑三个特例空数组、只有单个元素、极端值比如跳跃游戏里所有值都是1。这三个特例能挡住90%的边界错误。5. 常见误区与避坑心得从假贪心到真二分5.1 三个经典反例贪心失效的边界刷贪心题最大的坑不是不会写而是“什么都想用贪心”。我整理三个最经典的反例每一个都能让你对贪心的边界有新的认识。第一个是带权重的活动选择活动加上权重之后按结束时间排序的贪心策略就不再最优因为一个时间短但权重低的活动可能挡住一个时间长但权重高的活动你必须用动态规划。第二个是非标准面额找零假设纸币面额只有1、5、11要凑15贪心会先拿11然后需要1111一共5枚但555只要3枚贪心当场失败。这个例子说明了局部最优优先拿最大面额并不等于全局最优。第三个是0-1背包如果物品可以分割按单位价值排序贪心是对的但每个物品只能整件拿走时贪心就会失效因为“拿一个高性价比大件”可能塞不下而“换几个小件”反而能塞满背包。这三个反例告诉你一个共同规律贪心失效的根源都在于“局部选择会改变后续可选项的集合”。一旦出现这种耦合就要考虑动态规划或搜索了。提示遇到一个想用贪心的问题先花两分钟尝试构造反例。构造不出来再谈证明构造得出来直接转向其他算法。这两分钟往往会帮你省下几小时的错误方向。5.2 爱吃香蕉的狒狒贪心还是二分答案Hot 100相关讨论里经常被问到“073爱吃香蕉的狒狒”也就是LeetCode上那个狒狒吃香蕉的题N堆香蕉每小时最多吃某一堆里的k根如果这堆少于k根吃完后这一小时剩余时间就歇着求能在H小时内吃完所有香蕉的最小k。很多人第一反应是“吃得越快越好”试图用贪心推k但这题恰恰不是贪心而是二分答案。原因很简单这里不是“选什么顺序吃”的问题而是“给定一个k能不能在H小时内吃完”的可判定问题。每个k对应一个结果k越大越快吃完这个单调性让二分成立。check函数就是遍历所有香蕉堆把每堆需要的小时数累加向上取整判断总小时数是否不超过H。代码很短但思路和贪心完全不同。def minEatingSpeed(piles, h): def can_finish(k): return sum((p k - 1) // k for p in piles) h lo, hi 1, max(piles) while lo hi: mid (lo hi) // 2 if can_finish(mid): hi mid else: lo mid 1 return lo区分贪心和二分答案我总结了两个信号贪心问的是“按什么顺序安排这些选择”二分答案问的是“这个参数取多少能满足条件”。前者需要证明局部最优能导出全局最优后者只需要验证单调性。题型特征典型关键字对应算法求选择顺序、安排方案的最优最多、最少、能否满足全部贪心求某个参数的最小/最大值最小速度、最大容量、最短时间二分答案选择之间互相影响、需要回退背包、权重、代价状态动态规划5.3 刷题顺序与复盘方法Hot 100贪心这部分我建议按入门到进阶的顺序刷先做455分发饼干和860柠檬水找零这两道帮你建立“局部最优”的直觉再做763划分字母区间和435无重叠区间掌握区间排序然后上55、45、122、134这一组序列贪心感受“维护边界”和“差分累加”的思维方式最后刷406根据身高重建队列体会排序规则设计对贪心的重要性。每道题做完我建议你顺手写一个五行的复盘笔记题目是什么、贪心策略是什么、一句话证明思路是什么、时间空间复杂度是多少、你的代码在哪个边界上差点出错。这个模板看起来很笨但刷完这十几道题你回头看会发现它们之间的共性比你想象中大得多复盘笔记能帮你在周赛里快速完成模式匹配。我个人做Hot 100贪心这部分时最大的体会是贪心题的代码长度和思维成本完全不成正比代码越短越要警惕“我是不是碰巧过了”。所以每道题我都强迫自己补一句证明哪怕是口头复述。这样坚持下来后来遇到周赛里的包装题我第一反应不再是“这题我好像见过”而是“这个局部选择会不会让后面的选择变差”——这比记住一百道题更重要。