贪心算法实战：删数问题与单调栈优化详解

1. 问题引入从键盘到算法的删数博弈刚接触信息学奥赛的同学大概率会在贪心算法的章节里遇到这道经典题目“删数问题”。题目描述很简单给你一个位数不超过250位的正整数k和一个需要删除的数字个数s要求删除s个数字后剩下的数字按原次序组成一个新的正整数并且这个新数要尽可能小。题目链接对应着《信息学奥赛一本通》的1321题和洛谷的P1106题。我第一次看到这个题目时直觉想法是“删掉最大的s个数字不就行了”。但很快就被样例打脸了。比如数字178543要删掉4位。如果删掉最大的4个数字8,7,5,4得到13。但显然更优的解是删掉7,8,5,4得到13吗不对让我们仔细算算。178543删掉7,8,5,4后剩下1和3是13。但最优解其实是143等等我们需要一个系统的方法。这恰恰是这道题的魅力所在它完美地诠释了“局部最优”与“全局最优”的关系是理解贪心算法思想的绝佳入门案例。它看起来是个字符串处理问题但内核是一个关于“选择”的决策问题。我们不仅要在竞赛中解决它更要理解其背后的决策逻辑这种逻辑在后续处理更复杂的调度、优化问题时依然适用。接下来我将拆解这道题的完整解决思路从暴力搜索的直觉开始逐步优化到高效的贪心单调栈实现并分享我在调试和边界处理上踩过的坑。2. 核心思路拆解为什么不能简单删除最大数字我们先从一个更小的例子开始彻底弄懂问题的核心。设数字为n 14329s 2即删除2个数字。错误思路删最大数字是1,4,3,2,9最大的两个是9和4删除后得到132。手动尝试找最优我们的目标是让剩下的数字序列尽可能小。由于数字顺序不能变高位的数字对数值大小的影响是决定性的。因此核心策略应该是尽可能让高位的数字变小。让我们模拟一个决策过程从左边第一位高位开始看数字是1。我们要删除2个数字目前一个都没删。我们有没有可能通过删除1后面的一些数字让一个比1更小的数字来到第一位呢不可能因为1已经是当前最小的数字了后面是4,3,2,9。所以第一位锁定为1。现在考虑第二位。剩下的数字序列是4329我们还需要删除2个数字因为第一位1被保留了。第二位当前是4。我们看看4后面有没有比4小的数字有3和2。如果我们删除4那么3就会来到第二位。这会让整个数从14xxx变成13xxx显然是更优的。所以我们应该删除4。决策逻辑对于当前正在查看的位置如果它后面的数字比它小那么删除当前这个较大的数字让后面较小的数字“升”上来就能使最终结果更小。删除4后数字变为1329我们已经用了1次删除机会还剩1次。现在序列是1,3,2,9我们接下来看第二位现在是3。第二位是3它后面有比它小的2。删除3让2上来数字变为129。用了第2次删除。得到结果129。我们验证一下所有可能删除(4,9)-132删除(4,3)-129删除(4,2)-139删除(1,4)-329... 显然129是最小的。我们的决策过程找到了最优解。这就是贪心算法的核心每一步我们都只考虑“让当前高位尽可能小”这个局部最优目标。具体操作就是从左到右遍历数字维护一个结果序列。对于当前数字如果结果序列的末尾数字比当前数字大且还有删除次数那么就删除末尾数字因为删除这个大的可以让后面相对小的顶上来使得高位更小。重复这个过程直到不能删除为止。如果遍历完还有删除次数没用完就从序列末尾删除因为此时序列已经是非递减的末尾是最大的。这个操作模式非常像维护一个单调栈——我们希望栈内的数字从底到顶是单调不降的。一旦遇到比栈顶小的数字就弹出删除栈顶直到栈顶不大于新数字或删除次数用完。3. 算法实现详解从伪代码到AC代码理解了单调栈贪心思想后我们来实现它。输入是一个字符串num因为250位远超整数范围和一个整数s。3.1 算法流程步骤化初始化创建一个空栈可以用数组或字符串模拟stk来存放最终结果。remain_to_delete s。遍历输入字符串对于num中的每一个字符digit a.关键循环弹栈当栈不为空且栈顶元素 digit且remain_to_delete 0时 - 弹出栈顶元素相当于删除了一个数字。 -remain_to_delete - 1。 b.入栈将当前digit压入栈中。注意这里有一个细微但至关重要的点。即使当前digit是‘0’只要满足弹栈条件也应该进行弹栈操作。例如num“10023”, s1遍历到第二个‘0’时栈顶是‘1’‘1’ ‘0’且还有删除次数那么弹出‘1’第二个‘0’入栈结果是“0023”处理前导零后是“23”。如果因为digit是‘0’就不弹栈结果会是“1023”这就错了。处理剩余的删除次数遍历完成后如果remain_to_delete 0说明栈中的序列已经是非递减的比如12345此时要使得数最小应该从末尾高位数字已固定删除末尾对高位影响最小删除。直接移除栈末尾的remain_to_delete个字符。处理前导零将栈转换为字符串。删除字符串开头所有的‘0’。处理全零情况如果步骤4的结果是空字符串说明最终结果是0应输出“0”。输出结果。3.2 C 代码实现与逐行解析#include iostream #include string using namespace std; string deleteDigits(string num, int s) { string stk; // 用字符串模拟栈stk的末尾就是栈顶 int remain_to_delete s; for (char digit : num) { // 贪心当栈顶数字比当前数字大且还有删除次数就弹出栈顶删除大的 while (!stk.empty() stk.back() digit remain_to_delete 0) { stk.pop_back(); remain_to_delete--; } stk.push_back(digit); // 当前数字入栈 } // 如果遍历完还有删除次数没用完例如原数字是递增的如12345 // 直接从末尾删除因为此时栈内序列是非递减的末尾最大 if (remain_to_delete 0) { stk.erase(stk.end() - remain_to_delete, stk.end()); } // 处理前导零 size_t nonZeroStart 0; while (nonZeroStart stk.size() stk[nonZeroStart] 0) { nonZeroStart; } string result (nonZeroStart stk.size()) ? 0 : stk.substr(nonZeroStart); return result; } int main() { string k; int s; cin k s; cout deleteDigits(k, s) endl; return 0; }代码关键点解析while (!stk.empty() stk.back() digit remain_to_delete 0)这是贪心的核心。三个条件缺一不可栈不空有东西可删、栈顶比当前大删除能使高位变小、还有删除额度。stk.erase(stk.end() - remain_to_delete, stk.end())string的erase方法用于删除剩余字符。stk.end()是指向末尾的迭代器。前导零处理使用while循环找到第一个非零字符的位置nonZeroStart。如果nonZeroStart等于字符串长度说明全是零输出“0”。3.3 一个完整的演算示例以num “178543”, s 4为例我们走一遍算法当前digit栈stk (栈底-栈顶)remain_to_delete操作说明初始[]4‘1’[1]4栈空直接入栈‘7’[1,7]4栈顶17不弹栈直接入栈‘8’[1,7,8]4栈顶78入栈‘5’[1,7,5]3栈顶85弹栈8remain3。新栈顶75弹栈7remain2。新栈顶15停止弹栈5入栈。‘4’[1,5,4]1栈顶54弹栈5remain1。新栈顶14停止4入栈。‘3’[1,4,3]0栈顶43但remain0无法弹栈。3入栈。遍历结束[1,4,3]0剩余删除次数为0无需操作。处理前导零“143”无前导零。最终结果为“143”。你可以验证这确实是最小值。4. 边界条件与常见“坑点”实录这道题思路清晰后代码不难但边界情况非常考验细节。以下是几个极易出错的点我都曾在这里栽过跟头。4.1 坑点一前导零的处理时机与逻辑这是最常见的错误。必须在删除操作全部完成后最后一步处理前导零。绝对不能边删除边处理或者在栈操作中忽略‘0’。错误做法在入栈前判断如果digit是‘0’且栈为空就不入栈以为能跳过前导零。这会导致删除次数计算错误。例num”10023”, s1。正确结果是”0023”-”23”。错误逻辑读第一个‘1’栈空入栈。读第二个‘0’栈非空但digit是‘0’如果因为栈空时不入栈‘0’的逻辑这里会忽略。实际上我们应该用贪心规则栈顶‘1’ ‘0’且remain1所以弹出‘1’然后‘0’入栈。这样栈变成了[0]。后续操作得到”0023”。正确做法如前文代码所示将所有数字包括‘0’一视同仁地参与单调栈的贪心比较。最后再将结果字符串前面的‘0’全部去掉。4.2 坑点二删除次数用不完的情况如果原数字序列本身就是非递减的如”12345”那么遍历过程中的while循环一次都不会执行。如果s2遍历后栈为”12345”remain_to_delete2。错误做法不处理直接输出”12345”。正确做法算法步骤3直接从字符串末尾删除剩余次数的字符。”12345”删除末尾2位得到”123”。因为在高位已固定的情况下删除末尾最大的数字能使剩下的数最小。4.3 坑点三结果为全零的判断处理完前导零后字符串可能为空。例如num”1000”, s1。贪心过程‘1’入栈遇到第一个‘0’弹出‘1’‘0’入栈。后面‘0’,‘0’依次入栈因为栈顶‘0’不大于新‘0’。栈为”000”。删除剩余次数remain_to_delete0不操作。处理前导零删除所有‘0’结果字符串为空。此时必须输出”0”而不是空字符串。否则会WAWrong Answer。4.4 坑点四字符串与数字的混淆题目明确说明位数可达250位这远远超出了任何标准整数类型long long约19位的范围。因此必须用字符串string来接收和存储输入的数字。所有的比较、删除操作都在字符串上进行。比较字符‘5’和‘2’时比较的是它们的ASCII码对于数字字符来说是等价的但心里要清楚我们是在处理字符。5. 算法正确性证明与贪心策略的理解为什么这种“见大就删”的贪心策略能得到全局最优解我们可以这样理解决策的高位优先原则对于一个数字其大小首先由最高位决定。因此我们的首要目标是让最高位最小。在删除次数固定的情况下我们应该把删除的机会“用在刀刃上”即优先用来降低高位的数字。单调栈的局部最优性我们从左到右扫描。假设当前扫描到位置i栈内保存了前i-1个数字中在已执行了若干次删除后所能形成的、且满足“栈内单调不降”的最优前缀序列。现在考虑第i个数字num[i]。如果num[i]大于等于栈顶直接入栈保持了栈的单调性且没有浪费删除机会去删除一个可能使高位变大的数字。如果num[i]小于栈顶说明栈顶元素是一个“高位上的大数”。删除它如果还有机会让更小的num[i]占据这个位置对于这个特定的高位位置来说是立刻得到改善的。而且这个决策是“安全”的因为我们只删除了一个已经存在于结果中的、相对较大的数字换上一个更小的对于已经固定的更前的高位没有影响。无后效性这个决策是“向前看”的。删除栈顶一个已确定的高位数字不会影响后续的决策因为后续决策只关心剩下的数字序列和剩余的删除次数。它不会导致未来出现一个本该被删除的更大数字因为这次删除而“逃过一劫”。因此每一步都采取“当栈顶大于新数字时则弹出栈顶”的局部最优策略最终累积起来就是全局最优解。这个证明虽然不形式化但非常有助于我们直观把握贪心算法的精髓。6. 性能分析与拓展思考时间复杂度每个数字最多入栈一次、出栈一次所以时间复杂度是O(n)其中 n 是输入数字的位数≤250。这对于题目限制来说是绰绰有余的。空间复杂度主要使用了模拟栈的字符串空间复杂度为O(n)。拓展思考如果要求删除后数字最大怎么办只需将贪心策略反向维护一个单调不增的栈。当栈顶小于当前数字且还有删除次数时弹出栈顶。其余逻辑不变。如果数字中有前导零输入时就有我们的算法已经包含了处理逻辑因为输入是字符串开头的‘0’也会被当作普通字符处理。例如”00123”, s1算法会正确输出”0123”-”123”。更复杂的变种如果删除规则不是指定删除个数而是指定删除某些特定数字或者要求删除后数字是某个数的倍数等那就需要用到动态规划等其他算法了。这道“删数问题”是贪心算法的一个经典教学案例。它告诉我们面对一个优化问题时先分析影响结果的关键因素这里是高位数字然后设计一种每一步都朝着优化该因素方向前进的策略单调栈维护最小高位并小心验证边界条件前导零、剩余删除次数往往就能得到一个简洁高效的解法。在竞赛中遇到类似“构造最小/最大序列”的问题时不妨想想是否能用这种“单调栈贪心”的思路来解决。