上个月帮几位朋友看算法实验作业他们在头歌平台上刷贪心算法关卡卡得最久的不是那些需要长篇大论设计的题目而是一道看起来非常简单的删数问题。代码量不到二十行解题思路也说得头头是道可提交上去就是有测试点过不去。我翻了他们的代码几乎所有人第一版都是同一个思路——每次删掉当前数字里最大的那一位。这个直觉太正常了但恰恰是这道题设计得最精妙的地方。贪心算法这个系列写到第3篇我觉得是时候把删数问题拿出来彻底讲透了。它表面上是数字游戏实际上考察的是你对贪心策略本质的理解每一步的贪到底应该贪什么局部最优又是凭什么能推出全局最优这篇文章会从底层原理讲起完整推演删数问题的正解和反例再把前导零、k值边界这些坑挨个填平最后分享一下我在头歌这类评测平台上实测总结出来的经验。无论你是刚开始学算法的学生还是准备面试的开发者这篇都能帮你省下不少试错时间。1. 贪心的本质每一步都选当前最好凭什么最终一定最好1.1 两个决定性性质贪心选择与最优子结构贪心算法的定义听起来像废话每一步都做出当前状态下最好的选择希望通过一系列局部最优解拼出一个全局最优解。但它能成立是有前提的这个前提比算法本身重要得多也就是两个性质——贪心选择性质和最优子结构。贪心选择性质的通俗解释是你可以通过一次当前看起来最好的选择直接构造出全局最优解的一部分并且这个选择不需要回头修正。最优子结构说的是做出这次选择之后剩下的子问题仍然是同类型的优化问题而且子问题的最优解可以直接接在刚才的选择后面组成原问题的最优解。很多初学者只记住了每一步选最优这句话完全没验证这两条性质就套算法结果就是各种WA。我见过一个很典型的现象同学们在做区间调度问题时知道要按结束时间排序做删数问题时知道要删某个特殊位置但你要是问他为什么大多说不上来。这就是没把贪心选择性质吃透。这里可以打个比方。自助餐取餐如果你能来回走那当然可以每样都尝一口再决定但如果规则是只能往前走不能回头每个窗口只能拿一次且必须按顺序拿那么看到喜欢的就拿就不一定是最优策略——你可能在第一个窗口就装满盘子后面出现更好的菜只能干瞪眼。这个只能往前走不能回头的限制恰恰是很多贪心题目里的隐含约束你的选择会锁死后面的可能性。反过来如果一个问题的子问题是相互独立的并且每次选择不影响后续状态空间的结构那贪心就很可能是对的。贪心算法看似简单难就难在判断它是否真的适用。删数问题就是一个绝佳的检验样本它有明显的当前位置选择意味但正确策略不是凭直觉能直接看到的。1.2 找零钱反例看起来很贪结果翻车在正式拆解删数问题之前我先讲一个经典的反例帮你建立对贪心可能失效的敏感性假设有面值为1、5、11的硬币要凑出15元最少需要几枚按直觉的贪心策略每次选不超过剩余金额的最大面值先拿11剩4只能拿四个1一共5枚硬币。但显然更优的答案是拿三个5只需要3枚。贪心错在哪错在11这一枚虽然单次省了硬币数但它把剩余空间挤压得只能靠大量小面额来填充破坏了后续步骤的灵活性。这个例子和删数问题的共同点是单步看起来最优的选择对全局来说可能是一种伤害。在贪心算法里你要权衡的不是这一步消掉了多少而是这一步之后剩余问题是不是更容易解决。理解了这一点删数问题就不难破了。2. 删数问题完整推演从删最大的直觉误区到单调栈解法2.1 题目模型为什么数字很大时要当字符串处理删数问题的标准描述是给定一个n位正整数允许删去其中k个数字要求剩下的数字按原来的左右次序组成一个新数使这个新数尽可能小。有些平台还会要求输出最小数去掉前导零。读题第一件事不是想算法而是想清楚数据范围。注意n位正整数这个表述在很多评测平台里这个n可以到10万甚至更大long long根本存不下所以输入必须用字符串处理。这一点非常关键我在头歌平台上做这道题时第一版的代码里如果真的用整数类型读取大数测试点会直接爆掉或者TLE——爆掉是因为溢出TLE是因为字符串转整数再逐位处理会多出一堆无意义的运算。所以正确的模型是输入数字字符串输出经过删除操作后的最小数字字符串。整个算法只处理字符之间的比较不涉及真正的数值运算。2.2 第一个错误直觉每次删最大数字几乎所有初学者看到这道题的第一反应都是想让剩下的数最小那每次删掉当前最大的那一位不就行了这个直觉来自一个朴素观念——最大数字对数值的贡献最大删掉它数值下降最多。但这是一个典型的错误贪心。我用一个最小反例说明数字是213k1。按删最大策略删掉3得到21。可正确答案是删掉2得到13。13比21小得多。问题出在哪在于数字的大小是位置相关的。最高位上的数字差1整个数可能差出几个数量级最低位上的数字差1只是差1。所以删除的优先级应该优先考虑位置权重而不是数字面值。213这个例子里删掉最高位的2最高位从2降到了1整个数的量级直接掉了一档而删掉3只是动了最低位数字还是二十多。这也是每次删最大数字会翻车的原因它只看数字本身的大小完全忽略了位置权重。这个反例一定要牢牢记在心里面试或者考试里考官特别喜欢拿这种例子来测试你对贪心策略的理解深度而不只是测试你会不会背代码。2.3 正确贪心策略删除第一个下降点正确的策略是把整个数字看成一个从左到右排列的序列然后思考为了让最终的数最小我们希望最高位尽可能小其次是次高位以此类推——本质上是在做字典序最小化。具体做法是从左往右扫描找到第一个满足 a[i] a[i1] 的位置删除 a[i]。为什么是这个位置因为 a[i] 之前的所有数字都是小于等于后一个数字的这意味着前面的序列是单调不减的。如果我们在 a[i] 之前删掉某个数字这个位置的数字会变成后面更大的那个数整体字典序反而变大而删掉 a[i] 之后原本更小的 a[i1] 会补到这个高位上整体字典序在尽可能高的位置上变小了这是收益最大的一种删法。如果整个序列已经是单调不减的比如12345那就直接删掉最后一位。因为这种情况下没有任何下降点可以利用对数值影响最小的选择就是去掉最低位。用178543k2来走一遍完整过程第一轮序列 1 7 8 5找到第一个下降点是 8位置在第三位删除8得到17543。注意此时1 7但7 5所以下一轮的下降点是7。第二轮序列 1 7 5找到下降点7删除7得到1543。最终答案是1543。对比一下每次删最大数字在这个例子上会得到什么最大的数字是8删完得到17543再删最大数字是7得到1543。巧了这个例子里两种策略的结果一样。这也是为什么很多人用类似178543这样的随机例子去测测不出自己的错误——你随手造的数据往往掩盖了策略缺陷。这也是我强调要用213这种小反例来验证算法的原因。2.4 朴素实现与单调栈实现理解了正确策略之后实现就顺理成章了。最朴素的方法是把删除过程重复k轮每轮都从左向右扫描找下降点复杂度是O(nk)。n很大的时候这个复杂度撑不住需要优化成单调栈写法。单调栈的思路非常优雅维护一个栈遍历原数字的每一位。当栈非空、栈顶数字大于当前数字并且还有剩余删除次数时说明我们找到了一个高位数字大、低位数字小的结构这时候弹出栈顶相当于删掉了一个下降点。处理完之后把当前数字压入栈。如果遍历完还有剩余删除次数就从末尾依次弹出因为此时序列已经单调不减只能删末尾。Python版本是这样的def remove_k_digits(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) while k 0: stack.pop() k - 1 result .join(stack).lstrip(0) return result if result else 0C版本也不复杂#include bits/stdc.h using namespace std; string removeKDigits(string num, int k) { string st; for (char c : num) { while (k 0 !st.empty() st.back() c) { st.pop_back(); k--; } st.push_back(c); } while (k 0) { st.pop_back(); k--; } int pos 0; while (pos st.size() st[pos] 0) pos; string res st.substr(pos); return res.empty() ? 0 : res; }单调栈的每个字符最多入栈一次、出栈一次整体复杂度O(n)空间复杂度O(n)。从O(nk)降到O(n)这个优化在头歌这类平台的数据规模下几乎是必须的。顺带说一下很多平台的题解里会把这道题归类为贪心栈原因就在这里贪心决定策略栈负责高效执行策略。3. 删数问题的边界陷阱与头歌平台实测细节3.1 前导零最容易让你WA的隐藏条件删数问题上最常见的WA原因不是思路错了而是前导零没处理好。题目说剩下的数字按原顺序组成的新数如果一个数删完之后开头出现了0这个0算不算有效数字绝大多数题目的约定是不输出前导零但如果全部删完只剩0输出0。我用100200k1来演示。按贪心策略扫描1 0第一个下降点是1删掉它剩下00200。这时候如果直接输出00200某些评测点会判错正确做法是去掉前导零输出200。还有一个更隐蔽的情况如果删除后所有位都是0比如100200k3删除过程会得到0000去掉前导零后是空串最后要返回0。这个空转0的逻辑很容易漏我在实际评测里见过不少人在这里栽跟头。这里我非常建议你在代码里固定写一行result result.lstrip(0) return result if result else 0这行的含义就是把前导零全部去掉如果结果为空就补一个0。用一行代码把边界情况兜住不要靠多个if分支去判断逻辑越少越不容易出错。3.2 k等于n、k等于0与全零串边界条件里还有几个极端情况必须单独想清楚。第一种是k等于0。这说明不需要删除任何数字直接原样输出。单调栈代码能自动处理这种情况while循环不会执行只是把原数字全部压栈最后原样返回所以就算你不写特判也不会错。第二种是k等于n甚至大于n。所有数字全删光结果是0。处理方式就是在删除循环结束后如果栈空了最后返回0。单调栈版本在k循环中会弹空栈吗不会因为for循环里压栈的元素数量是有限的while k 0只会在栈非空时弹出。如果k等于n遍历结束后再执行末尾弹出循环最后栈空result为空串返回0。 第三种是输入本身就是一串0比如00000k2。遍历时栈顶是0当前也是00 0不成立所以不会弹出任何字符最后结果是00000去掉前导零为空串返回0。这个逻辑也是自动正确的。这些边界情况并不是出题人刁难你而是真实业务里一定会遇到的状态。写算法题的时候养成分情况测试的习惯能省下很多调试时间。3.3 头歌平台判题细节与典型关卡头歌EduCoder这类实训平台和LeetCode不一样它通常不是一个函数接口让你补全而是完整地读取标准输入、输出标准结果按关卡逐个评测。我在上面做贪心算法实验时总结了几个容易出问题的细节。第一输入格式不一定是一行数字一行k。有些关卡把n、k和数字串放在同一行用空格分隔有些分两行建议写代码时直接用cin或者input读取然后按实际格式做split。多读一行或漏读一行都会导致整个关卡全红。第二输出末尾的换行。头歌的评测脚本对空白字符虽然通常宽容但有少数关卡会严格要求输出不含多余空格或换行。稳妥的做法是只输出结果字符串末尾加一个换行即可不要额外打印调试信息。我在调试阶段曾经因为多打印了一行答案是导致所有测试点判错那一次的经历让我以后都记得先删掉调试输出再提交。第三一些关卡会要求输出最小数但不会在题目描述里明确写去掉前导零只会在样例里暗示。比如样例输入100200 1样例输出是200而不是00200这就说明平台期望的结果是去除前导零的。如果样例输出里带了0你再决定要怎么处理一切以样例为准。头歌平台的贪心实验题目通常不只有删数问题还会包括活动安排、最优装载、哈夫曼编码这些经典题但删数问题往往是第一关或者第二关卡住很多人。这关过了后面的题目如果也是贪心思路就可以顺势用同样的分析方法去做。4. 判断一个题目能不能贪心的实用准则4.1 适合贪心的三类问题场景刷题刷多了你会发现适合贪心的题目其实有迹可循主要集中在三类场景。第一类是区间调度问题。典型代表是给定若干活动的开始和结束时间选择最多数量的互不重叠活动。这类题目的贪心依据是按结束时间最早的活动先选因为结束得越早留给后面的时间越多。这几乎就是贪心选择性质的标准演示。第二类是排序后按某种规则逐个处理的问题。比如删数问题本质上是找一种特殊的删除顺序还有任务调度里最短处理时间优先的策略。这类题目通常需要你先想清楚一个比较规则然后按这个规则排序再逐个处理。第三类是可以分解成独立子问题的构造类题目比如哈夫曼编码、部分背包。部分背包区别于0-1背包的地方就在于物品可以分割所以按单位价值排序后从高到低取就行贪心成立。识别这三种场景能帮你快速建立直觉但最终还是要验证你的贪心选择之后剩下的子问题是不是仍然能用同样的策略如果可以贪心基本就成立了。4.2 不适合贪心的高频陷阱题有适合贪心的就有不适合贪心的。我最常拿来举例的是0-1背包和带特殊面值的找零钱。0-1背包每个物品只能选或不选不能分割所以按性价比从高到低拿不一定最优。原因很简单一个单位价值很高的物品可能体积也很大选了它之后剩余的容量无法再装其他组合整体收益反而下降。这个结构和贪心的独立选择条件冲突。找零钱的反例我在前面已经讲过。面值1、5、11凑15贪心得到5枚最优是3枚。这类问题如果面值满足特定条件比如任意连续面值之间存在倍数关系时贪心可能是对的但题目不会每次都给你这么友好的条件。这些反例的共同特征是什么是当前的最优选择会对后续选择产生不可逆的限制。如果每一步的选择都会改变未来的可选空间那你必须考虑全局而不是只看眼前。这就是为什么动态规划在这些题目上表现更稳定——它会显式地枚举所有可能状态。4.3 判断工具交换论证法与归纳法那么做判断时不靠猜靠什么算法竞赛里常用两个正式工具交换论证法和数学归纳法。交换论证法的思路是假设存在一个最优解它和贪心解不同。找出第一个不同的位置然后把最优解里的选择替换成贪心选择证明替换之后的解不会比原来的最优解差。如果每一步都能这样替换最终就把最优解改造成了贪心解说明贪心解也是最优的。删数问题就可以用这个思路证明。假设最优解中没有删除第一个下降点a[i]而删除了后面的某个位置a[j]。那么在删除后的序列里位置i上的数字仍然是较大的a[i]而如果我们删掉a[i]位置i上的数字会变成较小的a[i1]。其他位置保持不变。因为a[i1] a[i]删掉a[i]得到的新数一定更小与最优解矛盾。这个证明就论证了删除第一个下降点确实是必需的。数学归纳法则是另一种思路先证明第一步贪心选择后剩余问题仍然是同类型问题然后假设对于规模较小的输入贪心正确由归纳假设推出规模较大的输入也正确。两种方法本质上都在检验同一个问题贪心选择是否真的能安全地把问题规模缩小。我自己的经验是日常刷题不必每次都用严格证明但至少要做到能举出一个有说服力的反例说明别的策略是错的能让别人信服你的策略是对的。这样心里才踏实而不是我感觉应该能过。5. 贪心算法的性能优化与刷题实战经验5.1 时间复杂度的优化取舍回归到删数问题很多人在头歌平台上第一次提交用的是朴素的双重循环版本就是外层循环跑k次、内层循环找下降点。小数据安然无恙一旦数据规模上去比如n10^5、k5*10^4内层每次扫描O(n)总共要执行O(nk)次那就是50亿次操作任何一个评测系统都会超时。所以我说如果题目中n能到10^5级别贪心策略的部分就值得用单调栈来优化。单调栈写法不仅快代码也更短、更容易理解。不过我提醒一句如果只是初学阶段建议先把朴素版本写一遍再用单调栈版本优化。因为朴素版本最贴近你脑子里对删除下降点这个策略的直观理解它能帮你验证思路等其他题你能脱口而出维护单调性的时候再直接写单调栈也不迟。从复杂度的角度做一个对比实现方式时间复杂度空间复杂度适用场景朴素删除法O(nk)O(n)n和k都很小、教学演示单调栈法O(n)O(n)n和k很大、评测平台这个表格已经足够说明问题。在正式竞赛或评测平台上默认你至少应该给出O(n)级别的解。5.2 用暴力对拍验证贪心正确性说到验证思路我最推荐的方法不是盯着样例看而是写一个暴力的对拍程序。所谓对拍就是同时运行两个程序一个是你的贪心解另一个是你确定不会错的暴力解例如枚举所有删除组合然后用随机生成的小数据反复比较两者输出。比如删数问题删除k位等价于保留n-k位你可以用组合数枚举所有保留方案找出最小的那个作为暴力答案。n很小的时候这个暴力解一定是对的。然后用随机生成的数字串和k值让贪心解和暴力解各跑一遍如果输出不一致说明你的贪心策略有问题这时候再针对不一致的输入做分析。对拍的价值在于它能自动找到你手工测试时发现不了的反例。我前面用的213这个小反例就是靠类似思路发现的随机数字串特别容易生成这种高位数字不大但删除它能带来更大收益的输入。有一段时间我不管做贪心题还是动态规划题都会先写一个暴力版放着等正式解法写完直接对拍。这样做的好处是提交之前就把绝大多数逻辑错误挡在门外而不是靠评测系统告诉你错了再反复猜。5.3 我实测中整理的一些经验清单最后把我这次在删数问题上的经验整理成一个清单基本都是代码之外的坑也是我在头歌平台上一次一次试出来的。第一读入数据后先判断k的大小。如果k n直接输出0不要走算法因为走完还是会得到0但提前return能避免一些隐形的索引问题。k 0则直接输出原串。第二删除过程中的字符比较直接比较ASCII值即可数字字符0到9的ASCII码是连续的直接用 比较没有问题不需要转换成整数。第三处理前导零时使用语言内置的trim后置逻辑最省事。Python的lstrip、C手动跳零都可以关键是空串兜底输出0这一步不能漏。第四提交前删掉所有调试打印语句。头歌的后端评测通常只认标准输出的内容多任何一个字符都可能造成误判。第五如果在一个关卡里反复失败先检查是不是输入格式理解错了再看样例输出是否去除了前导零最后才怀疑算法本身。算法错误的概率没那么高格式问题反而最常见。第六做完删数问题之后建议顺手做一下它的变体删去k个数字使得剩下数字组成的数最大。做法就是对偶一下——把找下降点删除改成找上升点删除代码几乎一样。这个变体能帮你进一步巩固维护单调性这个核心思想。我在实际使用中的一个体会是贪心算法最容易翻车的地方从来不是代码写不出来而是凭直觉选了一个看起来很合理的贪心策略然后花大量时间在错误方向上debug。删数问题教会我的不是该删哪一个数字而是每一步的贪到底应该贪哪一位。这个优先级判断比任何模板都值钱。如果你最近也在刷贪心算法建议把这道题反复做三遍第一遍按你自己的思路写第二遍用单调栈优化第三遍尝试证明为什么正确。三遍下来你对贪心选择性质的理解会完全不一样。