贪心算法大概是所有算法专题里最“反直觉”的一个。明明每一步都只盯着眼前的最优解最后却常常能交出全局最优的答卷可换一道题同样的“眼前最优”又会把你带进沟里。这个专题二我想集中拆一类特别典型的贪心场景单调区间的收割以及分类极值的贪婪。这两个词不是严格意义上的术语是我自己做题过程中总结出来的“题感关键词”。先说清楚它解决什么问题。刷题时你大概率遇到过这几类题给一串数字删掉 k 个使结果最小、在时间轴里安排最多的不重叠会议、允许反复买卖股票时求最大利润、从一堆带截止时间的任务里挑出最多能完成的数量。它们表面看起来毫无关系实际上共享同一套思考骨架要么在某个单调方向上做连续的局部取优要么把数据按类别拆开、在每一类里贪心挑选极值。本篇会把这四类模型逐一拆开讲透配上可直接运行的代码、推导过程和我在实际调试中踩过的坑。适合准备算法竞赛、刷面试题或者刚学完基础数据结构想进阶的读者。我并不打算罗列“贪心模板”那没有意义。我更想讲清楚两件事为什么在这些题里“贪”不会出错以及在哪些变形题里“贪”会立刻失效。把这两条线摸熟以后再遇到新题你至少能判断它值不值得往贪心方向想。1. 先想清楚贪心为什么能收割单调区间1.1 贪心的本质与适用范围贪心算法的核心是一句话每一步都做当前看起来最好的选择并且不回头修改之前的选择。这句话听起来简单实际用起来经常翻车。问题在于绝大多数情况下局部最优不会自然等于全局最优。举个生活化的例子你今天逛超市看到打折就买最后钱包空了、东西也没用上而规划购物清单的人虽然每次挑选时看起来“束手束脚”最终却买齐了真正需要的东西。这就是“贪心失败”和“规划成功”的差异。那什么时候贪心才成立我在做题后的体会是贪心成立的问题几乎都满足两个隐藏条件之一选择的交换性你选择 A 而不是 B不会对后面可选的集合造成破坏也就是任何解里把 B 换成 A 依然合法且不会更差。决策的单调性局部收益的叠加方向和全局目标完全一致趋势只往一个方向走不存在“先牺牲后面才能获得更大收益”的情况。“单调区间”之所以能被贪心收割就是因为单调序列天然满足第二个条件。在单调递增区间里每一步正收益加起来就是总收益在单调递减区间里每一步规避亏损也能避免总亏损。趋势已经锁定局部判断就不会背叛全局。1.2 单调区间上的“局部最优”为何等于全局最优我们用一条股票价格曲线来直观理解。“可以多次买卖股票每次只能持有一股”这个问题我见过很多人第一次做时都会纠结要不要等涨到最高点再卖卖出以后要不要等跌到底再买实际上把价格序列看成若干段单调区间后答案就变得非常简单。比如价格是7, 1, 5, 3, 6, 4上升段在1 - 5和3 - 6。如果你只在 1 买入、5 卖出利润是 4在 3 买入、6 卖出利润是 3总利润 7。但贪心做法是只要明天的价格比今天高就默认“今天买、明天卖”把每天的差价累加。这样算出来是(5-1) (6-3) 7和掐头去尾做波段的结果完全一致。为什么因为“在第 i 天买入、第 j 天卖出”的利润price[j] - price[i]可以拆成中间每一天相邻差的和price[j] - price[i] (price[i1] - price[i]) (price[i2] - price[i1]) ... (price[j] - price[j-1])所以与其费劲寻找每一个单调上升区间的两端不如在区间内部把每一段“正相邻差”都收割掉。这就是单调区间收割的实质在单调不减的趋势里每一个局部正收益都不应该被放弃。这个结论在整个专题里反复出现。后面讲删数问题、会议安排时你会发现它们背后都是同一句话既然趋势已经明确那就把每个局部最优焊进最终答案里。2. 删数问题一张单调栈结构看透贪婪的取舍2.1 问题定义与暴力思路先看一道我最早接触贪心时反复做错的经典题给定一个非负整数构成的字符串num可能很长不能直接转成整数要求删掉k个数字使剩下的数字组成的整数尽可能小。比如num 1432219, k 3答案是1219num 10200, k 1答案是200注意前导零会被自然忽略。这类题在很多在线评测平台的头歌贪心专题里都能看到变体有的要求删掉后最大有的要求保留恰好 k 个数。暴力思路是枚举所有删 k 个位置的组合检查每种组合的结果取最小值。组合数是C(n, k)当n 1000, k 500时这个数字大到宇宙毁灭都算不完。所以必须找规律。我们先退一步思考一个最小规模的问题给定两个相邻的数字a和b谁该被删直觉上如果a b那么为了得到一个更小的数应该删掉a让b前移。因为数字高位越小整个数越小高位从a变成b且b a无论后面是什么结果都变小了。这个判断就是贪心决策的原型从左往右看如果当前位置的数字比它后面的数字大删掉它一定是划算的。2.2 单调不减栈的贪心推导把上述思路持续应用就会得到一个非常优雅的数据结构单调不减栈。从左到右扫描数字栈里存的是“已经决定要保留的数字”并且从栈底到栈顶保持单调不减。每来一个新数字c做一次循环判断如果还能删k 0并且栈不为空并且栈顶数字大于c说明把栈顶这个“高位大数”删掉让更小的c取代它的位置结果一定更小。重复上述过程直到栈顶不再大于c或者删满了k个。把c压入栈中。扫描结束后如果还没有删满k个说明数字已经是单调不减的比如12345这时从末尾直接删掉剩余的位数即可。因为末尾是最大位权位置删末尾对数字值的影响最小。为什么栈顶大于当前数字就一定要删这里可以再深入一层。假设当前栈是[4, 5]新数字是3此时如果保留4得到的前缀可能是453如果删4得到的前缀是353删5得到453顺序不能乱。比较来看删4得到的353明显小于453。因为4在更高位上把高位变小是收益最大的操作。同样的逻辑递归向上直到栈顶不大于3为止。2.3 完整实现与边界处理直接给一份 Python 实现用列表模拟栈def removeKdigits(num: str, k: int) - str: stack [] for c in num: while k 0 and stack and stack[-1] c: stack.pop() k - 1 stack.append(c) # 如果还没删够 k 个从末尾删 if k 0: stack stack[:-k] # 去掉前导零 ans .join(stack).lstrip(0) return ans if ans else 0这段代码有几个特别容易踩的边界坑我一个个说。第一个坑前导零。比如num 10200, k 1按贪心逻辑扫描到0时栈顶是11 0删掉1后面还有200最终结果看起来是0200。但用户要的是整数意义上的结果所以必须把前导零去掉输出200。如果所有数字都被删光前导零去掉后变成空串要返回0。第二个坑整数溢出。num可能长达数万位任何语言里的整数类型都装不下。所以全程用字符串比较和字符数组操作不要尝试int(num)。第三个坑k 可能等于len(num)。此时所有数字都应被删掉最终结果返回0。上面的stack[:-k]在k len(stack)时会得到空列表配合ans if ans else 0可以正确处理。2.4 变式一求最大数、变式二保留固定个数删数问题最妙的地方在于单调栈的方向反转一下就能从求最小变成求最大。求最小值用的单调不减栈栈顶小于等于新数字时保留求最大值则反过来用单调不增栈栈顶大于等于新数字时保留。核心逻辑是对称的想让数字尽量大就让高位尽量大所以一旦当前数字比栈顶大就考虑摘掉栈顶让更大的数字上位。def removeKdigitsMax(num: str, k: int) - str: stack [] for c in num: while k 0 and stack and stack[-1] c: stack.pop() k - 1 stack.append(c) if k 0: stack stack[:-k] return .join(stack)另一个高频变式是保留恰好 k 个数使得结果最小。这种题本质上和删除len(num) - k个数完全等价。想通这一点代码一行都不用改调用removeKdigits(num, len(num) - k)即可。很多同学在考场上绕不过这个弯非要自己另写一套循环反而容易出错。到这里你会发现删数问题就是“分类极值的贪婪”的一个绝佳样本每一轮面对“删栈顶”和“留栈顶”两个选项选更优的类别动作单调栈保证了这个分类决策可以在线性时间内互相衔接。3. 会议安排按边界分类取极值的典型模型3.1 从“区间不重叠”到右端点排序会议安排问题也叫最大不相交区间问题是另一类高频贪心模型。题目描述很直白给定若干个会议的开始时间和结束时间同一时间只能参加一个会议问最多能参加多少个完整的会议。我第一次做这道题时第一反应是按开始时间从早到晚排序然后依次检查能否接上。这个直觉非常自然但它是错的。我后面会给出反例。正确的贪心策略是按结束时间从早到晚排序每次选择结束时间最早且不与当前已选区间重叠的区间。为什么按结束时间排序因为一场会议结束后剩下的时间越多可供后续安排的余地就越大。结束时间越早就意味着为后面的会议省出了更多“可用区间”。这就像排队做核酸每个人占用窗口的时间越短后面能服务的人就越多。选择结束最早的会议是把“让后续选择空间更大”这个局部收益做到最大而这个收益不会损害之前已经做好的选择所以贪心成立。3.2 反例与正确性论证我先把那个让我栽过跟头的反例摆出来用数据说话。假设三个会议会议开始结束A812B910C1112如果按开始时间排序会先选 A8~12然后 B、C 都重叠只能选 1 个。但正确答案是先选 B9~10再选 C11~12能选 2 个。这个例子直观说明了按开始时间排序的错误早期选了一个“结束很晚”的会议会挡住后面所有本来能安排的会议。而按结束时间排序B 排在前面选完后剩余区间[10, ∞)足够容纳 C。严谨一点的证明可以用交换论证。假设某个最优解里选了一个结束时间很晚的区间X而全局结束最早的区间是Y。因为Y的结束时间不晚于X所以把X换成Y以后Y与X后面的区间依然不重叠。也就是说任何一个最优解都能被“替换”成包含最早结束区间的解且数量不变。这就证明了按结束时间选第一个区间是安全的接下来对剩余区间递归执行同样的逻辑就得到完整贪心策略。3.3 代码实现与复杂度实现非常短def maxMeetings(intervals): # intervals: list of [start, end] intervals.sort(keylambda x: x[1]) # 按结束时间排序 count 0 last_end float(-inf) for start, end in intervals: if start last_end: count 1 last_end end return count复杂度是 O(n log n)瓶颈在排序。实测下来这个代码在十万级数据量上运行也很轻松。注意start last_end的等号如果一个会议在上一场结束的同一时刻开始是合法的可以连续参加。很多题解里写成会漏掉这种边界白白丢分。我在牛客网刷题时就因为这个等号错过好几次提交。3.4 变体会议室数量问题与带权区间调度如果题目从“最多参加多少个会议”变成“这些会议至少需要多少间会议室”同样是区间模型但贪心策略完全不同。此时需要按开始时间排序用一个优先队列维护每间会议室当前的最早空闲时间每来一个新会议就把最早空闲的那间分配出去。如果最早的房间仍然不空闲就开新房间。这就是“分类极值”的另一种呈现把会议室看成类别每次贪婪地选择占用时间最短的类别资源。但还有一个反向的坑要提醒如果给每个区间加上权重要求选择总权重最大的不重叠区间集合贪心立刻失效。因为结束早的区间虽然省空间但权重可能很低牺牲一点空间选一个权重极高的长区间总收益反而更大。带权区间调度需要用动态规划或二分优化不能硬贪。认清这道分界线比多背十道模板题更重要。4. 股票买卖在单调涨价区间中贪婪收割4.1 问题建模把价格序列切成上升段股票系列题在面试里出现频率极高。最经典的入门题是给定数组prices其中prices[i]表示第 i 天的股票价格你可以多次买入和卖出但任何时候最多只能持有一股求能获得的最大利润。很多人第一反应是找局部最低点买入找局部最高点卖出然后不断重复。这个思路没错但写起来容易出错。因为“局部最低点”和“局部最高点”的判定在市场数据里边界情况特别多比如连续三个相同价格时哪里算峰、哪里算谷换个角度想把价格序列画成折线图它天然被切成一段段单调上升和单调下降的区间。贪心的逻辑特别简单在每一个单调上升的区间里每一天都做“今天买、明天卖”的操作把每天的价差收割掉在单调下降的区间里一天都不操作。为什么这个策略能得到最优因为任何一次完整的交易利润都能拆成相邻价差之和而相邻价差不为正的部分你永远没必要去承担。这等价于只保留所有prices[i1] prices[i]的差并把它们累加。事实上这是整道题所有解法里最简洁的写法。4.2 单次扫描写法代码短到让人怀疑def maxProfit(prices): profit 0 for i in range(1, len(prices)): if prices[i] prices[i - 1]: profit prices[i] - prices[i - 1] return profit用prices [7, 1, 5, 3, 6, 4]手动走一遍i11 7 不成立跳过i25 1加 4profit4i33 5 不成立跳过i46 3加 3profit7i54 6 不成立跳过最终结果 7就是我们在 1.2 节里拆解出来的两个上升区间的总利润。这段代码里没有任何递归、没有栈、没有 DP 数组但它就是对的。它抓住的本质是垄断式的单次交易也许要等大波段但无限制交易时小波段利润不会因为你的“合并交易”而增加。反过来把小波段利润全部收割恰好等于最优的单次波段交易。4.3 与单调区间的关系股票题是“单调区间收割”思想的最佳范例。你可以把它看成维护一个当前买入价遇到价格下跌就卖出如果之前买入了然后以下跌后的价格重新作为潜在买入点遇到上涨就一直持有。整个过程等价于切分价格曲线为多个单调不减段在每一段内做等差数列收割。我实测写这题时还试过用双指针维护局部峰谷代码量多出三倍而且很容易在处理连续相等价格时写错边界。后来想通相邻差分解法之后回头看峰谷写法实际上是在重复实现“切分单调区间”的过程只是绕了远路。如果面试时你能从“单调区间划分”的角度讲清楚解法面试官会明显更认可你的理解深度。4.4 陷阱手续费与冷冻期会让贪心失效我必须明确划出一条边界。如果题目加上“每次卖出要交手续费”或者“卖出后需要冷冻一天才能再买入”上面这段代码立刻失效。为什么因为手续费和冷冻期让交易不再是“独立可加”的。每次交易多了固定成本后过于频繁地收割小波段反而可能亏钱冷冻期让你无法在同一个上升段内相邻两天连续买卖。这时局部最优和全局目标之间出现了裂缝正确解法要退回到动态规划带手续费维护hold持有股票时的最大收益和sold不持有时的最大收益每步做状态转移。带冷冻期同理用两个或三个状态变量滚动更新。所以贪心和 DP 的边界从来不是靠“题目长得像不像”判断而要看局部收益能否无损耗地叠加。一旦出现固定成本、冷却时间这类“选择耦合”贪心就要让位。5. 优先队列分类极值的动态维护5.1 场景引入带截止时间的任务选择最后一种模型我认为是“分类极值贪婪”里最考验综合能力的它把排序、贪心和堆结合在一起。经典题目是这样给定若干课程每门课有持续时间duration和截止时间deadline你从时间 0 开始按某种顺序上课每门课必须连续上duration天并且在截止时间当天或之前完成。求最多能完成多少门课程。这个题我第一次看到时完全没思路。它和前面几个模型都不一样不仅要决定选哪几门课还要决定上课顺序而且选 A 不选 B 的影响并不直观。关键观察有两个如果已经决定要完成一个课程集合那么应该按截止时间从小到大上课这样最不容易超时。这本质上又是“让结束早的课先占用时间”和会议安排同源。在按截止时间排序后遍历的过程中每门课来临时我们把它的时长加入当前总时长如果超了当前课的截止时间就“退掉”一门已经选过的课时最长的课程。第二点是整个贪心策略中最“贪婪”的体现当选择空间超载时不是随机移除也不是移除最后加的而是移除花费时间最长的那门课因为这样能让当前已选集合的总时长最小同时课程数量不变。这就是用最大堆动态维护已选课程的极值。5.2 用最大堆替换最坏选择的原理把逻辑拆成三步对课程按截止时间deadline升序排序。维护一个变量total表示当前已选课程的总时长以及一个最大堆heap存储已选课程的时长Python 里用负数模拟。遍历每门课(duration, deadline)先假定选它total duration把duration压入堆然后检查total deadline是否成立。如果成立说明再不放弃一门课就会超时于是从堆里弹出最大的durationtotal - 弹出的值。为什么弹出最大时长一定最优因为超时意味着当前选课集合无法在截止时间前完成。既然必须放弃一门课放弃时长最长的那门课可以让总时长下降最多从而为后面的课程保留更多时间而课程数量只减一影响最小。这个决策不依赖于具体是哪门课只依赖时长所以用堆可以高效维护。一个反直觉的地方是我们放弃可能是“当前正在考虑的这门课”自己。比如现在只选了一门课时长已经超过截止时间那么弹出的就是刚压入的这门课相当于没选它。这个行为由堆自动处理不需要额外判断。5.3 实现细节与复杂度分析import heapq def scheduleCourse(courses): # courses: list of [duration, deadline] courses.sort(keylambda x: x[1]) heap [] total 0 for duration, deadline in courses: total duration heapq.heappush(heap, -duration) if total deadline: total heapq.heappop(heap) # 弹出的是负数加回去等于减去时长 return len(heap)这里的total heapq.heappop(heap)有点反直觉拆开写可能更清楚if total deadline: longest -heapq.heappop(heap) total - longest我一开始写的时候忘记把堆里的负数转成正数结果 total 越扣越离谱调试了半天才发现是符号问题。Python 的heapq是最小堆没有现成的最大堆用取反是标准做法但取反后弹出的值一定要记得再取反。复杂度是 O(n log n)。排序 O(n log n)每门课进出堆最多一次 O(log n)整体 O(n log n)。实测在n 10^5级别数据上运行非常流畅。5.4 这类模型的识别方法刷多了以后我发现“排序 堆替换”的模型有很强的识别特征题目要求“最多选择多少个元素”或“最小代价完成所有选择”每个元素有一个代价如时长、消耗的资源和一个上限如截止时间、容量限制元素之间存在某种线性推进关系如时间从 0 开始累加。一旦看到这三个特征就可以考虑先按上限排序再用堆维护已选代价超限就替换代价最大的元素。这个套路能解决大量看似杂乱的实际问题比如 CPU 任务调度、项目排期、广告投放组合等。它和前面“会议安排”的区别在于会议安排只需要选完就结束而堆替换模型允许你“反悔”先用堆留住所有候选再在超载时把最差的一个踢出去。这种带反悔能力的贪心其实是贪心思想的进阶形态。6. 常见误区与调试技巧实录6.1 误区一排序键选错会议安排按结束时间排序课程调度按截止时间排序但很多人在变式题里会惯性套错排序键。比如有一类题是“每个区间有价值选尽量多且价值最大”有人上来就按价值排序这显然不对因为价值最高的区间可能极长会挡住十个短区间。我的建议是在写排序前先在草稿纸上画一个反例问自己“如果我按这个键排贪心选第一个会不会导致后面选项变少”减损后续选择空间的排序键大概率是错的。6.2 误区二忽略空结果与前导零删数问题里返回空字符串还是返回0是提交正确率的分水岭。很多测试数据专门卡这个点num 10, k 2时答案是0不是空串。如果你在最后没有处理空字符串测试用例直接红一片。类似的边界还有删数问题里k为 0 时应该原封不动返回num扫描过程中栈为空但k还没用完时要继续往下扫而不是报错。多看几道题的边界条件后你会发现所有贪心题都有“边界三兄弟”空输入、全部删光、不删任何东西。6.3 误区三没验证贪心正确性就硬写这是我在训练营里看到新手最常犯的错。题目看起来能贪就直接套模板交上去结果 WA 了又不知道哪里错。我自己也吃过亏。后来养成一个习惯先用暴力或动态规划写出小规模正确答案再拿随机数据对比贪心结果。比如删数问题当字符串长度不超过 8 时可以用组合数枚举所有删除方案取最小值。然后生成一万组随机字符串把贪心结果和暴力结果逐个对比。如果全对再上提交如果不对立刻就能看到是哪种数据模式让贪心失败从而修正局部策略。import itertools import random def brute_force(num: str, k: int) - str: n len(num) best None for comb in itertools.combinations(range(n), n - k): s .join(num[i] for i in comb).lstrip(0) s s if s else 0 if best is None or int(s) int(best): best s return best # 随机对拍 for _ in range(10000): n random.randint(1, 9) num .join(str(random.randint(0, 9)) for _ in range(n)) k random.randint(0, len(num)) if removeKdigits(num, k) ! brute_force(num, k): print(找到反例:, num, k) break这种对拍脚本写一次只要十分钟但它能帮你确认贪心策略的正确边界比看十篇题解都管用。我在实际换题时遇到新模型也会先写一个 O(n^2) 的基线版本用它去校验 O(n log n) 的贪心版本。6.4 调试技巧打印每一步决策堆替换模型里最让我头疼的问题是“弹出元素后 total 对不上”。排查方法很简单在total duration和total - longest两处加打印把当前课程、堆内容、total 值全部输出。手动走两三个例子很快就能定位是符号问题还是逻辑问题。另外提醒一句不要在生产式调试里去脑补堆的内容。堆的内部顺序是层序存储肉眼很难直接看出最大值一定要用heap[0]加以验证。Python 里最大堆的堆顶是负数中的最小值也就是原始时长的最大值这个等价关系容易把人绕晕建议在注释里写清楚。可以说这个专题里我踩过的最贵的坑几乎都集中在“没验证反例”和“边界未处理”上。贪心思路想明白并不难但把它落实成一次提交就通过的代码考验的是细节功力。7. 写在最后我对贪心题的实操体会以我刷题的实际体感贪心专题最容易给人“虚假的掌控感”。题目看懂了思路也想通了代码一提交却总是差几个用例。后来我才意识到问题不在于贪心本身而在于没有把“局部最优为何等于全局最优”这个证明过程走完。每次拿到新题我都会在纸上写下三句话这个选择的局部收益是什么它会不会压缩后续选择空间是否存在交换性把别的解换成本步选择仍然合法如果三句话都能站稳再动手写代码。这个专题二里讲的四类问题“删数”“会议安排”“股票买卖”“课程调度”基本上覆盖了面试中九成以上的贪心基础模型。它们的共同点是在某一个单调维度上做极端值选择不同点是维护极值的数据结构从普通变量升级成栈再升级成堆。你可以把整条学习路径当作一次工具升级先从无结构数组里找极值再用单调栈在序列上维护极值最后用优先队列在动态集合中维护极值。如果这篇文章对你有帮助我建议你合上屏幕自己动手实现一遍这四个模型再尝试改造一两个变式。比如把删数题改成“保留 k 个数求最小”把会议安排题改成“最小的房间数”把股票题加上手续费再比较贪心与 DP 结果的差异。只有亲手写过、跑过、错过的题才会真正长成你自己的经验。未来遇到新题时你的第一反应不会是好慌而是这个题是不是又落在那片单调区间里。
