这一篇是贪心算法专题的第六篇也是整个系列的收官。前五篇我们磨了基础模板刷了经典例题也踩了不少证明上的坑。但说实话模板背得再熟碰到新题还是会慌因为贪心题最难的不是代码而是“怎么想到这个贪心策略”。今天这篇我想跳出题目本身把藏在贪心算法背后的两种思维聊透一件叫降维打击一件叫错位重构。顺手再用删数问题这条主线把两件事串起来让刚入门的朋友也能看明白。先交代这篇适合谁。如果你已经在刷贪心题但总靠记忆同类题来蒙策略或者经常出现“贪心策略看起来没问题提交就是过不了”的窘境这篇会给你一套完整的思考框架。如果你刚学完贪心基础也不用被“降维”“重构”这些词吓到它们只是两种具体的解题手段我会用非常直白的例子拆开讲。配合这个专题前五篇的内容这一篇算是把所有贪心的思考方式收束到一个位置上。1. 贪心专题收官先聊聊我对贪心的整体理解1.1 贪心不是“拍脑袋”局部最优与全局最优的辩证关系很多人初学贪心时觉得贪心就是“每一步选当前最好的”这话对但容易误导。真正可用的贪心策略并不是先射箭后画靶而是要先证明“每一步当前最好”确实能通向“全局最好”。这一点我在专题第一篇就强调过今天收官再展开讲一遍每一步都做局部最优选择最终得到全局最优解这件事需要两个前提——贪心选择性质和最优子结构。贪心选择性质是说局部最优的选择一定是某个全局最优解的第一个选择最优子结构是说做出这个选择后剩下的子问题仍然可以用同样的贪心策略继续处理。两个前提缺一个贪心就成了赌博。我习惯用一个下坡的例子帮助理解。假设你想从山顶走到山脚水库如果每一步都选最陡的下坡方向在理想地形下确实能走到最低点。但现实地形常有山谷和垭口一直选最陡坡可能把你带进一个低洼处那里不是全局最低点。这个例子不严谨但恰好说明了“局部最优不等于全局最优”的直觉来源。做题时如果只靠直觉选策略很容易被样例欺骗真正该做的是把“为什么局部最优能带出全局最优”用反证法或交换论证写清楚。1.2 贪心算法的适用边界什么题能贪什么题不能贪判断一道题能不能用贪心最有效的方法是先找反例。我刷题多年最常踩的坑就是看到一个题就条件反射地排个序然后从头扫到尾结果在某些边界数据上翻车。举个最经典的例子0-1背包问题不能贪心但分数背包可以贪心。同样是“每单位价值越高越好”的思路分数背包允许拆开物品所以局部价值最大可以无缝叠加成全局价值最大0-1背包不允许拆选了单位价值最高的物品后剩余空间可能装不下任何高价值物品反而让整体价值变低。这就是适用边界的问题。贪心题通常有个共同点决策之间不会“互相干扰”到无法修正的程度或者干扰可以被某种机制修正。一旦发现当前选择会永久性地破坏后面的可能性就要警惕这题是不是不能用贪心或者是否需要给贪心加上反悔机制。后面第三部分我们会专门讲“错位重构”其实就是在扩展这个边界——让贪心策略允许出错然后通过堆等结构把错误修正回来。1.3 专题脉络回顾从基础模板到两大进阶思维这个专题前五篇的内容我简单梳理一下脉络方便新读者定位。第一篇是贪心基础与证明方法讲了贪心选择性质和最优子结构并引入了交换论证。第二篇集中讲排序型贪心比如活动安排、会议室、最少箭射气球等区间类问题。第三篇讲的是带权调度和状态贪心比如任务规划、加油站问题。第四篇引入堆辅助贪心重点讲“当前最值”如何参与决策。第五篇开始涉及反悔贪心用一个动态维护的堆来撤销之前的决策。每一篇都有大量例题建议没看过的读者先补前面的内容。今天这第六篇要做的是把前面所有思维收拢成两个关键词。降维打击指的是把看似复杂的多维决策问题化简成“排序扫描”的一维问题错位重构指的是当贪心策略在局部做出了不够优的选择时通过额外的数据结构把这些选择替换或撤销从而把整体带回全局最优。接下来的每一部分我都会用具体题目来说明而不是空谈概念。特别是删数问题虽然题目本身不算难但它能同时把这两个思维展示得淋漓尽致所以我想把它作为整个专题的收官例题。2. 降维打击把复杂决策转成排序与扫描2.1 降维打击的核心把决策问题翻译成排序问题先说说什么叫降维打击。很多贪心题看起来要处理多个维度的信息比如每个任务有开始时间、结束时间、权重、价值每个物品有重量、体积、价值选起来要同时考虑好几个因素头脑很容易乱。降维打击的思路是找到其中一个最关键的量按它排序然后让剩余维度的信息在一次线性扫描中自然被处理掉。排序就是把一个高维决策空间压成一维的关键操作。为什么排序能起到这个作用因为排序后后续扫描只需要维护“截止到目前为止的状态”当前要做的决策通常只和上一个状态有关不需要回溯太多。以活动安排为例有若干个活动每个活动有开始时间和结束时间目标是选择尽可能多的互不重叠的活动。如果同时想开始时间和结束时间两个维度决策模型是二维的但一旦把所有活动按结束时间排序那么从早到晚依次扫描每次选择当前结束时间最早、且与已选活动不冲突的活动就能得到全局最多数量。这个结论的正确性可以用交换论证说明在任意一个最优解中如果把第一个活动换成所有活动中结束时间最早的那个肯定不会减少可选活动的数量。因为最早结束的活动只会更早让出时间不会让后面的活动失去机会。这就是“排序贪心选择”的降维威力——把“选哪些”变成“在什么时刻选哪一个”。如果你做题时发现题目里多个量纠缠在一起第一反应应该是思考排序依据放在哪个量上能让后面的一次扫描变得有决定性。2.2 区间类问题里的降维实例区间问题是降维打击最集中的战场。除了活动安排还有几个非常经典的变体无重叠区间、合并区间、最少的箭引爆气球、会议室最多容纳数量。这些题看起来解法各不相同但底层都是同一个动作——按端点排序再线性扫描。无重叠区间这题要求移除尽可能少的区间使得剩下的区间互不重叠。如果正面思考“移除哪些”选择空间很大但反过来想移除最少等价于保留最多这就直接转化成了活动安排问题。按结束时间排序后贪心地保留每一个不与上一个保留区间冲突的区间就是最优解。合并区间则是按左端点排序然后扫描时维护当前合并区间的左右边界遇到一个区间的左端点小于等于当前右边界就扩展右边界否则把当前区间收尾、开启新区间。最少的箭引爆气球这题我第一版做的时候也踩过坑。气球是水平区间箭垂直射出一支箭能射穿所有与之相交的区间。刚看到题时我想按左端点排序结果在范例之外的数据上出错。后来意识到应该按右端点排序每次从当前区间的右端点射出这样能保证这支箭穿过所有与它相交的后续区间数量一定是最少的。这个例子再次说明降维的关键不只是“排序”而是“选择哪个维度排序”。会议室问题同时最多有多少个会议则换了一种降维方式把每个会议的开始事件和结束事件拆成两个独立的时间点全部丢进一个数组排序然后扫描时遇到开始事件加一遇到结束事件减一过程中的最大值就是答案。这个“差分事件”的思路本质上也是把区间降维成端点的组合。区间题学到这里你会发现大部分都能归入“按右端点排序”或“按左端点排序合并”两个套路。2.3 从二维到一维坐标压缩与差分数组再往前一步有些区间问题数量很大直接扫描时间轴会超时。这时候要用坐标压缩和差分数组。讲个我刚工作时遇到过的例子多个直播房间的预约表每个预约是一个起止时间段需要算出哪个时间段同时预约的房间数最多。如果时间范围很大比如0到10^9直接开一个数组记录每个时刻的活跃数是不现实的。降维思路是这样的把所有区间的端点收集起来排序去重得到一个压缩后的坐标轴区间长度不重要重要的是端点之间的顺序关系。然后在压缩后的坐标轴上做差分每个区间在左端点位置加一右端点位置或下一个位置减一最后前缀和一遍就能知道每个离散区间的覆盖率。这样整个数据规模从时间范围降到了区间端点数乘2复杂度从O(T)变成O(n log n)。这种处理方式在贪心题的预处理阶段非常常用。比如活动安排需要判断某个时刻能否插入新活动比如任务调度需要统计某个截止时间前的已占用时间都可以先用差分数组快速得到全局状态。很多读者觉得差分数组是“数据结构题”的内容跟贪心无关其实不是。贪心算法经常需要快速获取“当前全局状态”差分数组、前缀和、扫描线都是让降维后的扫描保持高效的底层工具。3. 错位重构当标准贪心失效时怎么自救3.1 错位重构不是玄学而是允许贪心先犯错标准贪心最大的缺陷是“一步错步步错”。因为每一步都基于当前局部最优做决策一旦某一步的选择不是全局最优的一部分后面再怎么贪也补不回来。错位重构这个思路就是主动承认“我的选择顺序可能错位”然后引入一种机制在后续扫描时把错误的决策替换掉。它不是推翻整个贪心框架而是在贪心决策之后增加一个“纠偏操作”。我用一个非常直观的例子来说明。假设你要从一堆课程里选课每门课都有持续时间和截止日期你要在截止日期前完成课程才能算数目标是选尽可能多的课。朴素贪心会想按截止日期排序能上就上。但这样会出现问题一门持续时间很长的课占用了后续很多课程的时间明明可以为了多选几门课而放弃它。这个场景里之前“上了课”的选择就是错位的。错位重构的解法很巧妙仍然按截止日期排序逐个尝试加入当前课程同时用一个最大堆保存已选课程的持续时间。每加入一门课后如果目前累计耗时超过了当前课程的截止日期就把所有已选课程里耗时最长的那门弹出。这样等于在意识到“撑不住”时撤销了之前那个最不划算的选择。整个过程依旧是一次扫描却能把解从“局部最优”提升到“全局最优”。这种“先选进去超限后踢出最差的”模式就是错位重构最常见的实现。3.2 经典场景课程选择、股票交易、带惩罚的任务调度除了课程选择还有几个高频场景值得专门记一下。第一个是“股票交易II”的变体你可以无限次买卖但每次卖出要付手续费。很多人第一反应是“只要有利润就卖”但在有手续费的情况下有时不卖反而更优。这里就可以用错位重构的思路维护一个“当前最优买入价”同时记录“加上手续费后卖出是否比之前的状态更好”如果不卖更优就保留原状态。第二个是带截止时间和利润的任务调度问题每个任务有截止时间和完成利润同一时间只能做一个任务目标是利润最大化。朴素贪心按利润从高到低排序然后尝试把每个任务放到截止时间之前的空闲位置。这个解法本身不算错但如果任务数量很大逐个找空闲位置会很慢。错位重构的变体是按截止时间从小到大扫描用一个最小堆维护已选任务的利润当任务数超过当前截止时间时弹出利润最小的任务。因为截止时间限制了最多能同时排多少个任务超过就必然要放弃一个放弃利润最小的总是最优。第三个是“最多可以参加的会议数”和课程问题几乎一样但日期离散化更明显。你会发现这些场景都有一个共同结构有一个限制条件截止时间、容量、资源上限每次贪心加入一个候选一旦候选集合超出限制就踢掉集合中价值最差的一个。这里的关键就是“用什么标准衡量最差”课程问题踢掉耗时最长任务调度踢掉利润最小完全由题目的目标函数决定。3.3 堆是错位重构的最佳载体选大还是选小错位重构需要快速找到“该踢掉的那个”如果每次都用线性扫描找最值复杂度撑不住。所以这类题的标配是堆。但堆选型有个很容易记混的点什么时候用最大堆什么时候用最小堆我的记忆方法是这样的加入候选后超过限制时要踢掉集合中最差的那一个所以“最差”的定义决定堆的方向。课程选择里目标是最大化课程数量那么占据时间最多的课程就是最差所以用最大堆保存持续时间踢堆顶。任务调度里目标是最大化利润那么利润最低的任务就是最差所以用最小堆保存利润踢堆顶。反过来如果题目是“每个时刻选一个当前收益最大的任务”那就是最小堆还是最大堆要视“保留最优”还是“踢除最差”而定不要死记而是想清楚堆里装的是已选集合我需要快速拿到哪个极值。堆之所以适合做错位重构的载体是因为它支持“先临时接受再延迟否决”的机制。数组、栈都做不到在O(logn)内动态维护集合极值。前面我们提到贪心算法有时需要快速获取全局状态堆就是那个状态维护器。而且错位重构的思考顺序也很重要先想清楚“当前贪心决策可能错在哪里”再想“用什么数据结构能修正它”。如果倒过来先想用什么堆很容易被数据结构带着走反而做不出正确策略。4. 实战收官删数问题如何串起两大思维4.1 题目描述与暴力解法带来的直觉终于到今天的重头戏删数问题。题目描述非常简单给定一个以字符串形式表示的非负整数num要求移除其中k个数字使得剩下的数字按原次序排列后形成的整数尽可能小。num可以很长最多10^5位k小于num长度。比如num 1432219k 3答案是1219num 10200k 1答案是200而不是0200因为前导零需要去掉最终把0200处理成200。这题在很多刷题平台叫“移除K位数字”。看到这个题第一反应是暴力从n位里选k位删掉共有C(n,k)种方案n一大直接爆炸。但暴力不是没有价值。我建议读者先写一个枚举所有删除方案的暴力程序对随机小数据生成答案然后用它来观察一个规律。观察后你会发现最优解里被删掉的数字几乎都是“左边数字大于右边数字”的位置。比如1432219删掉4、3、2这三个位置正好是每一轮当前序列里第一个逆序对的左元素。这个规律引出了经典的贪心策略重复k次每次从左往右找到第一个满足num[i] num[i1]的下标i删除num[i]。为什么删除这个位置最优因为高位数字对数值大小的影响远大于低位从左往右第一个下降点就是“当前最高位处第一次出现不增反降”把这个高位数删掉能让剩余序列的高位立刻变小。每次删除都保证当前这一步的收益最大而且这个收益不会被后续操作破坏因为后续删除都发生在更低位。4.2 栈优化一次扫描完成所有逆序对删除上面的策略每次都要从最左重新扫描复杂度是O(nk)在题目的数据范围下不够用。我们需要把“重复k次扫描找逆序点”的操作优化成一次线性扫描。思路是把贪心过程压缩到一个单调栈里从左到右遍历每一位数字用一个栈保存“当前保留的最优前缀”每次遇到新数字时如果栈顶数字大于当前数字并且还有剩余删除次数就弹出栈顶这相当于执行了一次“删除左侧逆序对”的操作。为什么栈能等价替换原来的贪心因为那个贪心每次删除的是从左到右第一个逆序对的左元素而栈的弹出操作天然按照“当前扫描到右边更小的数字时左边较大的数字先被删除”的顺序进行正等价于从左到右处理逆序对。更妙的是如果一个数字弹出了栈说明它再也不会进入最终结果而如果扫描结束还有剩余删除次数说明序列已经单调不减这时最优策略就是删除末尾的剩余位数让最小的高位数字尽量保留。下面给出核心实现Pythondef remove_k_digits(num: str, k: int) - str: stack [] for ch in num: while stack and k 0 and stack[-1] ch: stack.pop() k - 1 stack.append(ch) # 如果还有剩余删除次数删掉末尾较大的数字 while k 0: stack.pop() k - 1 # 去掉前导零 res .join(stack).lstrip(0) return res if res else 0代码非常短但每一个细节都有讲究。比如弹出的条件必须是严格大于等于的时候不弹出因为两个相同的数字删除左边那个不会让结果变小所以没必要浪费删除次数。比如while循环里k要同时判断防止多删。比如最后要用lstrip(0)处理前导零如果全部删空就返回0。4.3 边界条件前导零、删光、k为0删数问题的边界条件是面试和笔试里最容易扣分的地方。第一类边界是前导零。原串里可能有0如果高位被删除剩下的0会跑到最前面必须去掉。很多人忘记这一步导致10200删除1位后输出0200而不是200。注意lstrip(0)在Python里会把000变成空串所以要额外判断空串返回0。第二类边界是k等于字符串长度。此时要删掉全部数字答案是什么题目通常规定“剩下的数字最小”既然全删了就返回0。这个case要在代码开头直接判断或者依靠最后res if res else 0兜住但显式判断更清晰也方便写注释。第三类边界是k0此时应该原样输出但由于可能存在前导零的原输入比如000123还是建议统一走一次处理逻辑。还有一类细节是数字很长直接用int会溢出或不必要所以全程保持字符串操作。这几类边界我在对拍暴力程序时都踩过。最隐蔽的是“栈里所有数字已经单调不减但k还没用完”的情况很多人会忘记末尾删除。其实只要想清楚单调不减序列里最小化结果应该删尾部删头部会让更小的数字提前不会变优但删尾部不会改变高位所以尾部是相对最优就不会漏掉这个while k0的循环。4.4 删数问题里的“降维”与“错位重构”到底在哪现在把删数问题放回今天的主线。降维打击体现在哪题目问的是“删除k个数字”这是一个组合选择问题选择空间是C(n,k)非常恐怖。但我们通过观察逆序对把它降维成一个“从左到右剪掉高峰”的扫描问题每处理一个字符只需要决定当前字符是否保留完全不需要关心后面那些还没扫描到的字符的排列组合。这就是降维——把数百万种删除组合压成一次性的线性决策。错位重构体现在哪看栈的工作方式就能感受到。遍历到新数字ch时如果发现栈顶比ch大说明之前把那个较大的数字保留进栈是一个“错位”的选择现在必须把它弹出去这个弹出过程本质上是在撤销之前的选择。比如1432219走到第二个2时栈里的4和3都被弹出用2替代这就是对早期决策的重构。贪心策略本身没有变变成的只是允许已经做出的选择在后续被替换掉。所以我一直觉得删数问题是用栈实现的贪心同时也是用栈实现的反悔贪心两者视角都对关键看你怎么理解它。5. 贪心题常见问题与调试心得5.1 三个最常踩的坑先总结一下我在讲解和刷题中看到的三个高频坑。第一个坑是“没有证明就开写”。很多题目的样例非常友好按直觉排序后样例能过但隐藏数据直接打脸。我自己的习惯是至少花三分钟想一个反例想不出来再动手实在想不出来就先写暴力对拍让对拍结果来验证贪心。第二个坑是排序依据选错这在区间问题里尤其明显。同样是区间活动安排按右端点排序合并区间却按左端点排序选错排序维度贪心直接失效。第三个坑是忽略边界条件。删数问题的前导零只是其中之一更普遍的情况是输入为空、所有元素都被删光、k等于0、n等于1等。很多读者代码主体写对了却在边界上交了学费。我在做对拍时发现边界数据往往最能暴露贪心策略的缺陷因为它会迫使你的代码走到正常路径之外的逻辑分支。建议每次提交前都想一遍算法在输入极端小、结果极端空、目标极端大时分别会做什么。5.2 调试贪心题的三板斧调试贪心题我常用的手段有三个按效率排序是小数据暴力对照、随机对拍、打表观察决策序列。小数据暴力对照是最快的验证方式把n控制在10以内暴力枚举所有方案再跑你的贪心比较答案是否一致。随机对拍是把小数据对照自动化用脚本生成大量随机测试样例循环跑贪心和暴力一旦发现不一致就固定住那一组数据人工分析。我强烈建议每个贪心题都配一个对拍脚本它比任何代码审查都靠谱。打表观察决策序列是对拍发现错误之后的第二步。不要只盯着答案不一致看把贪心每一步选了什么、决策时的状态都打印出来。例如删数问题可以打印每次弹出哪个数字、剩余k是多少。你会发现错误往往出现在“某个看似正确的局部选择把后面的机会堵死了”。到这一步通常就能定位是贪心性质不满足还是堆的极值方向选反了。对拍脚本本身不复杂随机生成输入、调用两个函数、比较输出几十行就能写完但它能省下大量在提交记录里挣扎的时间。5.3 一套可复用的做题检查清单最后我把这些年做贪心题沉淀下来的检查清单分享给大家。每拿到一道贪心题按顺序过一遍决策空间是什么如果选择组合数很大思考能否用排序把决策顺序固定下来。排序依据选哪个量选完之后能否用交换论证说明“相邻两个决策的顺序可以交换而不变差”。一次扫描中当前决策是否会永久影响后续决策如果会思考是否允许“先接受、后反悔”。如果允许反悔用一个堆来动态维护已选集合的最值并明确“最差”的定义。边界条件有哪些空输入、全部删光、k为0、长度1分别怎么处理。复杂度是否达标能在线性扫描中完成就不要套多层循环。最后写一个暴力对拍跑至少几百组随机数据再提交。这套清单不是万能药但它能帮你把一个模糊的“感觉能贪”变成可验证的“确实能贪”。我在带新人时经常说贪心题考的不是聪明而是“能不能把直觉翻译成可证明的策略”。多练几道题之后你会发现在看到题目的前几分钟内你已经在心里默默执行这套流程了。聊到这儿说说我自己的体会。刷了这么多年算法题贪心是我觉得“性价比”最高的一个专题因为代码短、思维密度高但也是翻车率最高的专题。降维打击和错位重构这两个词是我自己总结出来的看待贪心的角度不一定是什么标准术语但它们确实帮我解决了很多“明明会做模板却不会做题”的问题。最后再分享一个小习惯每次做完一道贪心题写一句话总结它“为什么能贪”。积累几十道之后你会发现贪心的套路真的就那么多剩下的全是证明功夫。