贪心算法专题写到第六篇不少读者私信问我系列都到收官了除了那句“每一步都取当前最优”的大实话还有没有更上层的思维模型可以带走。我的答案很明确有而且就两个词降维打击与错位重构。今天这篇终极收官我用删数问题贪心算法作为主线索把这两个思维模型彻底拆开揉碎顺便聊聊我在带算法训练营时总结出来的避坑套路。如果你正准备面试算法岗或者刚刚开始刷 LeetCode 的贪心题这篇内容可以把前面五篇零散的题型重新串成一张真正的网。先说降维打击是什么意思。很多贪心题表面上是让你在全局做选择所有排列、所有删法看起来都要枚举但仔细分析会发现真正决定胜负的往往只是某一个关键维度——比如字典序问题里的高位、区间问题里的右端点、跳跃问题里的最远可达距离。把这个维度抽出来全局决策就能被压缩成一条线上的一次扫描。再说错位重构有些问题允许甚至要求你改变原有顺序或者在一个大序列里重新选择一批元素贪心策略这时会变成一个自定义的比较规则让相邻元素按某种局部标准排列最后拼出全局最优。删数问题刚好横跨这两个模型所以我们把它当作这次收官的主菜。1. 贪心算法的底层逻辑为什么局部最优能通向全局最优1.1 贪心的“不后悔”特性和动态规划的分水岭贪心算法最容易被误解的一点是很多人把它理解成“聪明地枚举”。其实贪心是建立在一个非常强的假设之上的每一步做出当前看起来最好的选择之后绝不回头、绝不修改。这种“不后悔”特性是贪心和动态规划最大的分水岭。动态规划会保存所有子问题的状态之后每一步都可能利用之前的结果做递推贪心却只保留一个当前最优的局部状态一路滚下去。因此贪心的复杂度通常只有 O(n) 或 O(n log n)而动态规划动不动就是 O(n²) 甚至更高。最容易理解贪心的例子是排队接水。假设有 n 个人接水第 i 个人需要 t[i] 分钟目标是让所有人的等待时间总和最小。直觉告诉我们应该让耗时短的人先接。但为什么因为任意两个相邻的人 i 和 j如果 t[i] t[j]把他们的顺序交换两人及后面所有人的等待时间总和会减少。这个“相邻交换不劣”的论证几乎可以套用到所有基础贪心题。它说明贪心不是靠感觉而是靠目标函数的可分解性全局等待时间可以写成相邻顺序差的累加。也正是因为这一点贪心题才常常被放在动态规划的同一章里讲。动态规划允许你在岔路口走错一步后通过状态转移绕回来贪心则要求每条岔路都只走一次。换句话说贪心更像是一场“每一步都尽量不后悔”的决策游戏而动态规划是“后悔了也能通过状态回溯找到最优路径”的复杂工程。判断一道题到底该用哪种方法最简单的试金石就是看当前决策是否会影响后续可选范围如果会影响优先考虑动态规划如果不会或者影响方向完全可预期贪心就可以上场。1.2 降维打击的本质把全局目标拆成可验证的局部条件降维打击这个词在算法里指的不是炫技而是把高维的决策空间压缩成一维的线性判断。以删数问题为例一个 n 位数字删掉 k 位可能的删法数是 C(n,k)随 n 增大是指数级增长这是高维的枚举空间。但数字大小比较有一个独有性质从高位到低位逐位比较第一个不同的位置就决定了大小。换句话说比较两个删除方案时我们不需要看完后面所有位只要找到它们第一个产生差异的高位即可。于是问题从“删哪些数字”降维成“哪些高位的数字更小”决策维度变成一条从左到右的数轴。这个降维过程很像冒泡排序里的相邻逆序对。一串数字如果要变成有序不需要一次性决定所有元素的最终位置只要反复把相邻的逆序对交换最后整体就有序了。贪心删数也是类似的思路只要出现“前一个数字比后一个数字大”的逆序立刻把前一个删掉因为高位越小越好做完一次删除后继续看新的相邻关系直到删够 k 次。这个操作把指数级枚举压缩成一个线性扫描是典型的降维打击。还有一个更直接的理解角度把全局最优解想象成一条从起点到终点的路径降维就是找到这条路径的唯一“导航信号”。在删数问题里导航信号是“每次碰到下降沿就处理峰顶”在区间调度里导航信号是“每次选结束最早的区间”在跳跃游戏里导航信号是“维护最远可达边界”。一旦找到了这样的信号你就不需要再回头看整张决策表只需要跟着信号一步步走最后自然到达全局最优。这就是为什么很多贪心证明被称为“局部条件足够强”。2. 删数问题的降维打击从“删谁”到“删哪里”2.1 题目原型与直觉误区先上原型题给定一个以字符串表示的非负整数 num要求移除 k 位数字使得剩余数字最小并且保持原有数字的相对顺序。例如 num 1432219k 3一眼看上去容易认为要删掉最大的三个数字也就是 9、4、4于是得到 1221。但正确答案是 1219比 1221 更小。这个反例直接否定了“删最大值”的直觉。看出问题了吗数字大小不是由单个数字的绝对大小决定的而是由它的位置权重决定。十进制里高位的一个数字影响的是整个数量级。你把最高位的 4 删掉让第二位的 4 提前到高位和把低位的 9 删掉效果完全不一样。所以贪心时要比较的是“前一位是否比后一位大”而不是“当前数字是否总体最大”。这个误区是删数问题里最容易踩的第一坑。再验证几个边界样例。num 12345k 1 时没有逆序对应该删除最后一位得到 1234因为高位已经都是最小了只能动尾部。num 100200k 1 时删除第一位 1 得到 00200去掉前导零后是 200它比删除 0 得到的 10200 小得多。num 10k 2 时删除到空串按题意返回 0。这些小用例我每次讲课时都会先让学生手算因为代码写错最多的并不是主逻辑而是前导零和 k 达到长度后怎么办。2.2 从左到右的贪心判据逆序对必须优先删除为什么从左到右遇到逆序对时必须删除前一个数字这里做一个严格的位权论证。假设在原串中第一次出现 s[i] s[i1]也就是说第 i 位之前的所有数字都已经非递减。现在必须删除一个数字如果删除的是 i1 或者更靠后的某个字符那么 s[i] 仍然停留在第 i 位如果删除的是 s[i]会让 s[i1] 上升一位。由于 s[i] s[i1]删除 s[i] 后第 i 位变小了这是一个方向性的优势。又因为第 i 位之前的结果完全不变所以删除 s[i] 得到的数一定小于删除其他位置得到的数。也就是说第一个逆序对里的前一个字符是“当下必删项”。这里要特别强调“第一个”这个词。不是所有逆序对都同时处理而是只处理当前扫描中第一个发生的逆序。因为删除一个数字后它前面和后面的字符会变成新的相邻关系可能产生新的逆序也可能让原来的逆序消失。比如 1432219 里第一次看到的是 4 和 3删除 4 后序列变成 132219原本 4 和 3 的问题解决了但 3 和 2 又变成新的逆序于是继续删除 3。这种“边删边看新状态”的特点决定了不能用一次静态扫描定位所有删除点。这个证明看着简单但它给了我们一个可重复的决策规则只要还有删除名额就去删除当前能形成逆序对的那个较大的前驱。删完之后前面的数字又可能形成新的逆序所以需要反复比较上一位和当前位。最自然的实现是循环 k 次每次从头扫复杂度 O(nk)但用单调栈可以一趟搞定整体复杂度降到 O(n)。2.3 单调栈实现与边界条件先上 Python 实现这段代码也是很多面试题解的标准模板def removeKdigits(num: str, k: int) - str: if k len(num): return 0 stack [] for ch in num: while stack and k 0 and stack[-1] ch: stack.pop() k - 1 stack.append(ch) if k 0: stack stack[:-k] res .join(stack).lstrip(0) return res if res else 0栈里的字符始终保持从底到顶非递减。每次读入新字符 ch如果栈顶大于 ch说明它和 ch 构成了一个逆序立即弹出栈顶k 减一。这里弹出的字符可能是一个原本已经入栈的“高位偏大”的数字它被后面的小数字顶替正是贪心选择。扫描结束后如果 k 还没用完说明整个序列已经变成非递减此时要从尾部删除因为尾部数字在高位中占比最小删除尾部对结果影响最小。这段代码有四个边界要注意。第一k 大于等于原始长度时直接返回 0因为所有数字都会被删光。第二前导零必须去掉0200 要转成 200。第三如果去掉前导零后栈为空要返回 0而不是空字符串。第四Python 里stack[:-k]在 k 为 0 时会返回空所以必须先判断if k 0。我见过太多人在最后一步踩这个坑。单调栈的另一个好处是空间开销可控。最坏情况下需要把整个字符串都放进栈里空间复杂度 O(n)。很多变体题比如“去除重复字母使字典序最小”也是同一套栈模型只不过额外加了字符出现次数和是否已在栈中的判断。只要把删数问题的栈吃透这类题基本就是换皮。3. 错位重构当贪心决策改变原有顺序3.1 拼接最大数排序规则的“传递性”设计删数问题的对称面是拼接问题。给定一组非负整数让你重新排列它们的顺序使拼接后的整数最大。比如 [3, 30, 34, 5, 9] 的答案是 9534330而不是 9330534 之类。这类问题的核心不是选哪些数字而是给整个序列重新定义顺序也就是错位重构。两个数字谁应该放前面只需要比较两种拼接结果对于 x 和 y如果 xy yx那么 x 放在 y 前面会让整体字典序更大。把这种两两比较扩展成排序规则让整个数组按照这个规则排好再拼接就是最大数。直觉上这像一个冒泡过程任意一对相邻元素如果不满足“前面拼接后面更大”交换它们会让整体变大反复交换直到稳定全局最大。只要比较规则满足传递性排序后的结果就是全局最优。Python 实现也很直接from functools import cmp_to_key def largestNumber(nums): strs [str(x) for x in nums] def cmp(a, b): if a b b a: return -1 elif a b b a: return 1 else: return 0 strs.sort(keycmp_to_key(cmp)) res .join(strs).lstrip(0) return res if res else 0需要提醒的是这种比较器必须满足传递性排序算法才有意义。比如 x 需要排在 y 前y 需要排在 z 前x 也必须排在 z 前。如果自造一条不满足传递性的比较规则Java 会直接报 “Comparison method violates its general contract”Python 虽然不报错但排序结果可能不稳定。所以我建议在笔试环境里用s1s2和s2s1这种字符串拼接比较法既直观又安全。3.2 移除K位后的最小数为什么不能无脑删最大值同样是删除 k 位如果把题目的约束改成“删除后可以任意重排剩余数字”解法立刻变了。因为允许重构顺序时为了让剩余数字最小只需要保留数值最小的 n-k 个数字然后从小到大排列。这不再需要单调栈只需要一次计数统计复杂度 O(n)。对比下来你会发现经典删数问题的难点恰恰在于“不允许重排”它逼着你在固定顺序中做局部最优决策而拼接最大数则相反给定的是一个可以随便重排的集合。搞清楚题目到底允许不允许重排是决定贪心策略方向的第一个判断。问题变体是否保持原顺序贪心核心时间复杂度移掉K位数字保持单调栈删逆序O(n)删除K位后重排不保持计数保留最小 n-k 个数O(n)拼接最大数不保持自定义比较器排序O(n log n)从两个数组取数拼最大各数组内保持单调栈 按字典序合并O((mn)k)这张表把贪心的重构维度说得很清楚。“不能无脑删最大值”的本质是移除一个数字时你真正要改变的是某个位置上的数字而不是数字本身的大小。高位的 4 虽然比低位的 9 小但它占据的位权是 9 的上百倍。所以在固定顺序的题目里先处理逆序对再考虑删除末尾才是对位权的正确尊重。3.3 重构后的验证单调栈维护的妙用把删数和拼接组合在一起就会得到整个贪心专题里最有分量的综合题从两个数组中分别选取若干元素保持每个数组内部的相对顺序拼接成一个长度为 k 的最大数。以 nums1 [3,4,6,5]nums2 [9,1,2,5,8,3]k 5 为例答案是 [9,8,6,5,3]。解题思路是枚举第一个数组取 i 个数字第二个数组取 k-i 个数字对每个数组先用删数问题的单调栈方法取出长度为 i 的最大子序列然后合并两个子序列合并规则是每次比较两个序列剩余的字典序谁大取谁。这里最容易写错的点是合并时的比较。很多人以为双指针比较当前元素就行但在 [6,7] 和 [6,8] 这类例子中当前元素相同必须继续比较后面的每一位才能决定先取哪一个。换句话说合并本身也是一个贪心重构过程它的比较维度是整个剩余子序列而不是单个字符。这也是我常说的“错位重构”最考验细节的地方。这道题也验证了一个重要结论单调栈不只是删除类问题的工具它还能用来生成“保持顺序的最大子序列”。只要你把删数问题的判据反过来——遇到逆序对时删除较小的前驱保留较大的前驱——就能得到另一个方向的变体。我经常跟读者说贪心的魅力不只是会做一道题而是会用同一套底层规则推出一整类题。4. 贪心专题常见套路盘点与避坑指南4.1 贪心失效的典型场景贪心不是万能药。最经典的反例是换零钱问题货币面值有 1、3、4 元要凑出 6 元贪心策略会优先用 4 元得到 411 共三枚硬币但最优解是 33 两枚。为什么贪心失效因为选择一个 4 元硬币后剩余的 2 元无法用 3 元硬币补齐当前决策限制了后续选择。这类带有“后效性”的问题动态规划才是正解。0-1 背包问题也一样不能简单地按单位重量从大到小装因为一个物品要么拿要么不拿选了某个体积大的物品可能挤掉多个体积小但总价值更高的物品。所以适用贪心的问题通常有两个特征贪心选择性质即局部最优选择不会被后续选择推翻最优子结构即删掉这个局部选择后剩余子问题的最优解仍是原问题的一部分。如果一道题想不通它为什么满足这两个性质不要硬用贪心先用小数据暴力验证一下再说。4.2 实战中的经典母题区间调度、跳跃游戏、分发糖果题型贪心策略时间复杂度关键证明/易错点区间调度问题按结束时间升序选择不重叠的区间O(n log n)结束越早留给后续空间越大跳跃游戏维护当前能达到的最远坐标越界则失败O(n)只关心最远距离不关心具体路径最少跳跃次数在可达范围内选择下一步延伸最远的点O(n)边界是当前最远距离不是当前位置分发糖果两次相邻扫描取左右约束的最大值O(n)不能只扫一遍加油站统计总油量油量差为负则重置起点O(n)总油量小于总消耗则无解用最少数量的箭引爆气球按右端点排序重叠区间共用一箭O(n log n)注意区间边界是否算重叠这些母题里我特别想强调“最少跳跃次数”。它的贪心策略并不是每次跳到能跳得最远的那个位置而是维护当前这一跳的边界在边界内选出能让下一次边界最远的点。很多错误解法是直接递归或 DP其实一次线性扫描就够了。它和删数问题一样本质都是从“最优点”降维成“边界推进”。这也再次说明贪心题不是靠背题型而是靠识别决策维度。4.3 二分贪心 vs 单调栈贪心如何选择还有一类题目不是直接贪心而是先二分答案再用贪心验证。典型代表是“分割数组的最大值”把数组分成 m 段要求所有段和的最大值最小。这里贪心在验证阶段工作假设答案是一个数 X从左到右累加元素一旦当前段和超过 X 就切一段最后看切出的段数是否超过 m。二分不断缩 X 的范围直到找到可行且最小的 X。这种“二分答案 贪心验证”虽然听上去比单层贪心高级但核心仍是判断一个候选值可不可行决策同样是线性的。如何选择我的经验很直接如果题目问“能否达到”或“最大值最小/最小值最大”先想二分答案如果题目问“删除/保留某些元素且保持顺序”先想单调栈如果题目问“把序列重排成最大/最小”先想排序规则如果题目问“区间或资源筛选”先想按端点排序后扫描。这四类覆盖了贪心题的大半壁江山。5. 终极收官的刷题路线与面试表达技巧5.1 从基础到变体的刷题顺序很多读者问贪心题到底刷多少才算够。我的建议不是堆数量而是按决策类型分六轮。第一轮是热身做分发饼干、柠檬水找零、买卖股票的最佳时机 II感受“局部最优”和“反悔”的区别。第二轮做区间类比如无重叠区间、用最少数量的箭引爆气球习惯按右端点排序。第三轮做跳跃类把跳跃游戏、跳跃游戏 II 吃透。第四轮做删除类和字典序类移掉 K 位数字、拼接最大数、去除重复字母感受单调栈和自定义排序。第五轮做二分加贪心分割数组的最大值这类题理解“验证比选择更容易贪心”。第六轮再挑战综合题像从两个数组取数拼最大数。这六轮不一定按顺序死板执行但每一轮都要手写一遍而不是只看题解。每一轮的验证方式也不一样。热身题主要看边界条件区间题要画图理解“重叠”的定义跳跃题要模拟极端情况比如全 1 数组和 [2,3,1,1,4] 这种混合跳删除类题要对拍暴力枚举二分题要反复调整边界。如果你能把每轮里至少三道题完全靠自己想通贪心的手感基本就出来了。5.2 面试时如何讲清楚贪心证明面试里讲贪心最怕只甩一句“我贪心一下”。靠谱的表达分三步先给出贪心策略说清每一步选什么再用交换论证或反证法说明为什么不会变差最后说明复杂度。加一个示范对于拼接最大数如果贪心规则要求 x 在 y 前而最优解中 y 在 x 前由于 xy yx交换这两个相邻数字会得到更大的拼接结果与“最优”矛盾所以最优解必然满足贪心规则。这就是标准的交换论证。删除类问题则用位权论证删除更高位上的较大数字会让紧随其后的较小数字提升一位结果一定更优。两种证明都不需要长篇大论两三句话就能讲清。如果面试官追问“你的比较规则为什么能保证全局最优”回答的核心是“任何非贪心顺序都一定存在一个相邻逆序交换后结果不变差反复交换最终会变成贪心顺序”。这句话是几乎所有贪心证明的万能模板。除了证明还要主动提一下边界条件比如前导零、空串、比较器传递性这会让面试官意识到你不是背题而是真的踩过坑。5.3 踩坑记录与调试心得最后写点只有亲手写过才会知道的细节。第一个坑就是 Python 的切片stack[:-0]不是取整个序列而是空序列处理 k 剩余时要先判断 k 0。第二个坑是整数溢出和字符串转换拼接最大数绝对不能把两个数转成 int 再比较因为两个 10 位数字拼接会超过 32 位整数范围直接用字符串比较更安全。第三个坑是前导零结果 000 要输出 0否则会被判错。第四个坑是自定义比较器的传递性我已经在上面说过Java 环境会直接抛异常。还有一个通用的调试技巧我强烈建议每个贪心题都配一个暴力版。写一个递归枚举所有可能方案或全排列然后用随机小数据去对拍。比如删数问题暴力可以枚举所有删除组合拼接最大数可以枚举所有排列随机生成几十组小数据一旦暴力结果和贪心结果不同立刻能定位是策略问题还是实现问题。这个习惯帮我至少发现了五六个自以为正确、实际上反例藏在边角里的贪心设计。不要嫌麻烦对拍 10 分钟胜过查 bug 一小时。写到这儿贪心专题的第六篇就接近尾声了。我个人最想强调的一件事是别把贪心题当成“感觉题”去刷而是要始终问自己三个问题这个问题能降维成相邻比较吗题目允许重构顺序还是必须保持原顺序如果贪心挂了动态规划能不能兜底带着这三个问题去读每一道题比盲目刷五十道题有用得多。最后再分享一个小习惯我现在每做一个贪心题都会顺手写一个暴力解法来对拍哪怕不提交只要小数据能跑通就说明我是真的理解了这场降维打击和错位重构。希望这篇收官能帮你把整个贪心专题真正串起来。