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

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 = 14329，s = 2，即删除2个数字。

• 错误思路（删最大）：数字是1,4,3,2,9，最大的两个是9和4，删除后得到132。
• 手动尝试找最优：我们的目标是让剩下的数字序列尽可能小。由于数字顺序不能变，高位的数字对数值大小的影响是决定性的。因此，核心策略应该是：尽可能让高位的数字变小。

让我们模拟一个决策过程：

1. 从左边第一位（高位）开始看，数字是1。我们要删除2个数字，目前一个都没删。我们有没有可能通过删除1后面的一些数字，让一个比1更小的数字来到第一位呢？不可能，因为1已经是当前最小的数字了（后面是4,3,2,9）。所以第一位锁定为1。
2. 现在考虑第二位。剩下的数字序列是4329，我们还需要删除2个数字（因为第一位1被保留了）。第二位当前是4。我们看看4后面有没有比4小的数字？有，3和2。如果我们删除4，那么3就会来到第二位。这会让整个数从14xxx变成13xxx，显然是更优的。所以，我们应该删除4。
   • 决策逻辑：对于当前正在查看的位置，如果它后面的数字比它小，那么删除当前这个较大的数字，让后面较小的数字“升”上来，就能使最终结果更小。
3. 删除4后，数字变为1329，我们已经用了1次删除机会，还剩1次。现在序列是1,3,2,9，我们接下来看第二位（现在是3）。
4. 第二位是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 算法流程步骤化

1. 初始化：创建一个空栈（可以用数组或字符串模拟）stk来存放最终结果。remain_to_delete = s。
2. 遍历输入字符串：对于num中的每一个字符digit： a.关键循环（弹栈）：当栈不为空且栈顶元素 > digit且remain_to_delete > 0时： - 弹出栈顶元素（相当于删除了一个数字）。 -remain_to_delete -= 1。 b.入栈：将当前digit压入栈中。

   注意：这里有一个细微但至关重要的点。即使当前digit是‘0’，只要满足弹栈条件，也应该进行弹栈操作。例如num=“10023”, s=1，遍历到第二个‘0’时，栈顶是‘1’，‘1’ > ‘0’且还有删除次数，那么弹出‘1’，第二个‘0’入栈，结果是“0023”，处理前导零后是“23”。如果因为digit是‘0’就不弹栈，结果会是“1023”，这就错了。

3. 处理剩余的删除次数：遍历完成后，如果remain_to_delete > 0，说明栈中的序列已经是非递减的（比如12345），此时要使得数最小，应该从末尾（高位数字已固定，删除末尾对高位影响最小）删除。直接移除栈末尾的remain_to_delete个字符。
4. 处理前导零：将栈转换为字符串。删除字符串开头所有的‘0’。
5. 处理全零情况：如果步骤4的结果是空字符串，说明最终结果是0，应输出“0”。
6. 输出结果。

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为例，我们走一遍算法：

最终结果为“143”。你可以验证，这确实是最小值。

4. 边界条件与常见“坑点”实录

这道题思路清晰后，代码不难，但边界情况非常考验细节。以下是几个极易出错的点，我都曾在这里栽过跟头。

4.1 坑点一：前导零的处理时机与逻辑

这是最常见的错误。必须在删除操作全部完成后，最后一步处理前导零。绝对不能边删除边处理，或者在栈操作中忽略‘0’。

• 错误做法：在入栈前判断，如果digit是‘0’且栈为空，就不入栈（以为能跳过前导零）。这会导致删除次数计算错误。
  • 例：num=”10023”, s=1。正确结果是”0023”->”23”。
  • 错误逻辑：读第一个‘1’，栈空，入栈。读第二个‘0’，栈非空但digit是‘0’，如果因为栈空时不入栈‘0’的逻辑，这里会忽略。实际上，我们应该用贪心规则：栈顶‘1’ > ‘0’，且remain=1，所以弹出‘1’，然后‘0’入栈。这样栈变成了[0]。后续操作得到”0023”。
• 正确做法：如前文代码所示，将所有数字（包括‘0’）一视同仁地参与单调栈的贪心比较。最后再将结果字符串前面的‘0’全部去掉。

4.2 坑点二：删除次数用不完的情况

如果原数字序列本身就是非递减的（如”12345”），那么遍历过程中的while循环一次都不会执行。如果s=2，遍历后栈为”12345”，remain_to_delete=2。

• 错误做法：不处理，直接输出”12345”。
• 正确做法：算法步骤3，直接从字符串末尾删除剩余次数的字符。”12345”删除末尾2位，得到”123”。因为在高位已固定的情况下，删除末尾最大的数字能使剩下的数最小。

4.3 坑点三：结果为全零的判断

处理完前导零后，字符串可能为空。例如num=”1000”, s=1。

1. 贪心过程：‘1’入栈，遇到第一个‘0’，弹出‘1’，‘0’入栈。后面‘0’,‘0’依次入栈（因为栈顶‘0’不大于新‘0’）。栈为”000”。
2. 删除剩余次数：remain_to_delete=0，不操作。
3. 处理前导零：删除所有‘0’，结果字符串为空。
4. 此时必须输出”0”，而不是空字符串。否则会WA（Wrong Answer）。

4.4 坑点四：字符串与数字的混淆

题目明确说明位数可达250位，这远远超出了任何标准整数类型（long long约19位）的范围。因此，必须用字符串（string）来接收和存储输入的数字。所有的比较、删除操作都在字符串上进行。比较字符‘5’和‘2’时，比较的是它们的ASCII码，对于数字字符来说是等价的，但心里要清楚我们是在处理字符。

5. 算法正确性证明与贪心策略的理解

为什么这种“见大就删”的贪心策略能得到全局最优解？我们可以这样理解：

1. 决策的高位优先原则：对于一个数字，其大小首先由最高位决定。因此，我们的首要目标是让最高位最小。在删除次数固定的情况下，我们应该把删除的机会“用在刀刃上”，即优先用来降低高位的数字。
2. 单调栈的局部最优性：我们从左到右扫描。假设当前扫描到位置i，栈内保存了前i-1个数字中，在已执行了若干次删除后，所能形成的、且满足“栈内单调不降”的最优前缀序列。现在考虑第i个数字num[i]。
   • 如果num[i]大于等于栈顶，直接入栈，保持了栈的单调性，且没有浪费删除机会去删除一个可能使高位变大的数字。
   • 如果num[i]小于栈顶，说明栈顶元素是一个“高位上的大数”。删除它（如果还有机会），让更小的num[i]占据这个位置，对于这个特定的高位位置来说，是立刻得到改善的。而且这个决策是“安全”的，因为我们只删除了一个已经存在于结果中的、相对较大的数字，换上一个更小的，对于已经固定的更前的高位没有影响。
3. 无后效性：这个决策是“向前看”的。删除栈顶（一个已确定的高位数字）不会影响后续的决策，因为后续决策只关心剩下的数字序列和剩余的删除次数。它不会导致未来出现一个本该被删除的更大数字因为这次删除而“逃过一劫”。

因此，每一步都采取“当栈顶大于新数字时则弹出栈顶”的局部最优策略，最终累积起来就是全局最优解。这个证明虽然不形式化，但非常有助于我们直观把握贪心算法的精髓。

6. 性能分析与拓展思考

• 时间复杂度：每个数字最多入栈一次、出栈一次，所以时间复杂度是O(n)，其中 n 是输入数字的位数（≤250）。这对于题目限制来说是绰绰有余的。
• 空间复杂度：主要使用了模拟栈的字符串，空间复杂度为O(n)。

拓展思考：

1. 如果要求删除后数字最大怎么办？只需将贪心策略反向：维护一个单调不增的栈。当栈顶小于当前数字且还有删除次数时，弹出栈顶。其余逻辑不变。
2. 如果数字中有前导零（输入时就有）？我们的算法已经包含了处理逻辑，因为输入是字符串，开头的‘0’也会被当作普通字符处理。例如”00123”, s=1，算法会正确输出”0123”->”123”。
3. 更复杂的变种：如果删除规则不是指定删除个数，而是指定删除某些特定数字，或者要求删除后数字是某个数的倍数等，那就需要用到动态规划等其他算法了。

这道“删数问题”是贪心算法的一个经典教学案例。它告诉我们，面对一个优化问题时，先分析影响结果的关键因素（这里是高位数字），然后设计一种每一步都朝着优化该因素方向前进的策略（单调栈维护最小高位），并小心验证边界条件（前导零、剩余删除次数），往往就能得到一个简洁高效的解法。在竞赛中遇到类似“构造最小/最大序列”的问题时，不妨想想是否能用这种“单调栈+贪心”的思路来解决。