1. 项目概述从一道国赛真题看算法思维的深度与广度“最大的数”这道题是2022年第十三届蓝桥杯国赛C/C大学B组第四题。乍一看标题很多同学可能会觉得这又是一道关于大数运算或者贪心找最大值的题目但实际接触后往往会发现其精巧之处远超预期。它不像一些纯模拟题那样直白也不像某些动态规划题那样有固定的“套路”而是将数组操作、字符串处理、以及深度优先搜索DFS的思维巧妙地融合在一起考察选手对数据结构的灵活运用和对问题本质的洞察力。这道题之所以值得拿出来详细拆解正是因为它提供了一个绝佳的样本让我们看到在算法竞赛中同一个问题往往存在多种迥异但都行之有效的解法。数组解法直观高效体现了对数据特性的精准把握字符串解法则更贴近问题的“语义”操作起来别有洞天。今天我就结合自己多年刷题和带比赛的经验把这两种主流思路掰开揉碎了讲清楚不仅告诉你代码怎么写更重点剖析每种方法背后的设计逻辑、适用场景以及那些容易翻车的“坑”。2. 题目核心需求与场景解析2.1 问题重述与输入输出约定首先我们必须准确理解题目到底要我们做什么。题目通常会给出一个由数字字符组成的字符串或者等价的一个数字数组以及一个整数k。要求是从这个字符串中删除k个字符剩下的数字按原顺序组成一个新的数并且要使这个新的数尽可能大。输入格式一般第一行是一个字符串num表示给定的数字。第二行是一个整数k表示需要删除的数字个数。保证k小于num的长度。输出格式输出删除k个字符后能得到的最大数字字符串。示例 输入num “1432219”, k 3输出“4329”解释删除数字 ‘1’, ‘4’, ‘2’ 后剩下的数字“4329”是可能的最大结果。核心约束与场景顺序保留这是最关键的一点。你不能随意打乱数字的顺序只能通过删除操作来改变结果。这直接排除了排序等简单方法。删除固定数量k是预先给定的你必须恰好删除k个字符不能多也不能少。结果最大化目标函数非常明确就是让剩下的数字字符串表示的数值最大。对于长度相同的数字字符串比较大小就是简单的字典序比较从最高位开始逐位比较。潜在的大数数字可能很长比如1000位远超任何基本数据类型的表示范围因此我们必须全程用字符串或数组来处理不能转换成整数。这个场景非常经典它模拟了一种“资源有限下的最优选择”问题我们有一个序列数字需要移除一部分k个不良或次优的元素使得剩下的序列价值数值最高。它在金融优化投资组合、工程选择关键路径等领域都有抽象层面的对应。2.2 为什么贪心算法是可行的面对这个问题暴力搜索如DFS枚举所有删除组合在数据规模稍大时就会立刻超时。我们需要更聪明的策略。一个关键的观察是为了让最终的数字最大我们应该尽可能让高位的数字大。这引出了一个贪心策略从左到右遍历数字维护一个结果序列。对于当前遍历到的数字如果结果序列末尾的数字比它小并且我们还有删除名额k 0那么我们就应该删除弹出结果序列末尾的那个较小的数字因为把它留在高位相对当前位置会拖累整体数值。这个过程类似于维护一个单调非严格递减的栈。贪心正确性浅析假设有两个相邻的数字a高位和b低位且a b。如果只能删除一个数字那么删除a得到bX...肯定比删除b得到aX...更大因为最高位变大了。这个局部最优选择可以推广到全局。当然严格的证明需要数学归纳法但竞赛中理解到这个直观层面通常足够。3. 核心解法一基于数组/栈的经典解法这是最高效、最常用也最需要细致处理边界条件的方法。其核心是模拟一个栈用数组或vector实现通过单次遍历完成“删除”与“选择”。3.1 算法流程与代码实现我们使用一个数组或vectorcharstk来模拟栈它最终存储的就是结果数字的每一位。初始化空栈stk删除计数器del k。遍历输入字符串num的每个字符ch循环判断当栈非空 (!stk.empty())、栈顶元素小于当前字符 (stk.back() ch)、并且还有删除次数 (del 0) 时执行循环弹出栈顶元素相当于删除了它。删除次数del减一。入栈将当前字符ch压入栈中。处理剩余删除次数遍历完成后如果del 0说明字符串本身是递减或平缓的没有触发足够的删除这意味着我们需要从结果的末尾再删除del个字符。因为栈此时是单调不增的末尾的数字是最小的。处理前导零将栈中的字符转换为字符串。这里需要特别注意结果可能包含前导零比如输入”10200″, k1贪心过程可能得到”0200″。我们需要去掉前导零但如果结果为空应返回”0″。下面是 C 的实现代码包含了详细的注释#include iostream #include string #include vector using namespace std; string removeKdigits(string num, int k) { vectorchar stk; // 用vector模拟栈比直接操作字符串方便 int del k; // 剩余可删除次数 for (char digit : num) { // 关键贪心步骤当栈顶数字比当前数字小且还能删就弹出栈顶删除它 while (!stk.empty() stk.back() digit del 0) { stk.pop_back(); del--; } stk.push_back(digit); // 当前数字入栈 } // 情况1如果还有删除次数没用完从末尾删除因为栈现在是单调不增的 // 这对应原数字序列几乎完全递减的情况如 num”1234″, k2 if (del 0) { // 调整stk大小直接丢弃末尾的del个字符 stk.resize(stk.size() - del); } // 将栈中字符构建为字符串 string result(stk.begin(), stk.end()); // 处理前导零找到第一个非零字符的位置 size_t nonZeroPos result.find_first_not_of(‘0’); if (nonZeroPos string::npos) { // 如果全是零返回”0” return “0”; } // 返回去掉前导零后的子串 return result.substr(nonZeroPos); } int main() { string num; int k; cin num k; cout removeKdigits(num, k) endl; return 0; }3.2 数组解法的关键细节与避坑指南1. 循环条件的顺序至关重要while (!stk.empty() stk.back() digit del 0)这三个条件顺序不能随意调换。必须先判断!stk.empty()否则在空栈时调用stk.back()会导致未定义行为段错误。这是非常常见的运行时错误。2. 理解“删除”的语义在这个算法里“删除”并不是真的在原字符串上抹去字符而是通过“不入栈”或“从栈中弹出”来体现。stk中保存的就是我们选择保留的字符。这种“以存代删”的思想在很多算法题中都很有效。3. 末尾删除与单调栈性质遍历结束后进行if (del 0)的判断和处理是必不可少的。贪心过程保证了栈内序列是单调非增的因为遇到更大的数会把前面小的弹掉。如果还有删除次数说明整个序列下降不够“陡峭”无法消耗完k次删除那么最小的数字肯定在末尾直接从末尾删除即可。4. 前导零处理的陷阱这是本题最大的一个“坑”也是面试和竞赛中常见的考查点。贪心算法可能产生前导零比如输入num “100200”, k 1过程遇到第一个 ‘0’栈顶 ‘1’ ‘0’不弹栈。stk变为[‘1’, ‘0’]。继续遇到 ‘0’栈顶 ‘0’ ‘0’不弹栈… 最终栈为[‘1’, ‘0’, ‘0’, ‘2’, ‘0’, ‘0’]删除末尾1个del1得”10020″。但注意数字”10020″和”1002″在数值上是相等的吗不对”10020″去掉前导零后是”10020″而”1002″是”1002″我们算法得到的是前者。等等这里例子举得不好因为k1时正确结果应该是删除第一个 ‘0’得到”10200″。让我们看更典型的例子num”10200″, k1。贪心过程’1’入栈’0’入栈因为’1’’0’遇到’2’栈顶’0’ ‘2’且del1弹出’0’del0’2’入栈后面’0’, ‘0’依次入栈。最终栈为[‘1’, ‘2’, ‘0’, ‘0’]即”1200″。正确。 但前导零确实会发生例如num”10″, k1结果应该是”0″。我们的代码中stk最终为[‘1’, ‘0’]删除末尾1个不del在弹出时已用完。所以result”10″find_first_not_of(‘0’)找到位置1’1’返回”10″错了正确答案是删除 ‘1’留下”0″。问题出在哪我们的贪心逻辑stk.back() digit在’1’和’0’时不成立所以’0’被直接入栈了。这导致了错误。这说明我们的贪心条件stk.back() digit在某些情况下尤其是涉及0时可能不是最优的不对于”10″, k1删除 ‘1’ 得到”0″确实是最大因为只剩一位。但我们的算法得到了”10″。这暴露了一个严重问题我们的算法目标是让数字最大但当我们用stk.back() digit时我们只在“当前数字比栈顶大”时才替换。对于’0’它不会触发替换即使删除栈顶可能更好。等一下让我们重新审视经典的正确解法。我犯了一个错误。经典的“移掉K位数字”或“获取最大数”问题的贪心条件通常是stk.back() digit吗我混淆了“最大数”和“最小数”。经典题目“移掉K位数字”是求最小数贪心策略是遇到更小的就弹栈。而我们这里是求最大数策略应该相反当栈顶数字比当前数字小且还能删就弹出栈顶因为高位放个小数字不划算。所以条件stk.back() digit是对的。但对于”10″, k1’1’入栈。当前digit’0’栈顶’1’’1’ ‘0’假。所以不弹栈’0’入栈。结果栈[‘1’, ‘0’]即”10″。这显然不是最大因为”0″比”10″小不对我们要的是最大数。”10″和”0″比较”10″是两位数”0″是一位数在数值上10 0所以”10″更大。但题目要求删除k个字符k1。从”10″中删除1个字符可能的结果是”1″或”0″。”1″比”0″大。所以最大结果应该是”1″。我们的算法得到了”10″但”10″是原数没有删除任何字符这违反了删除k1的要求。问题在于我们的算法没有保证恰好删除k个字符。在”10″的例子中一次删除都没发生 (del始终为1)遍历结束后del1 0我们执行了stk.resize(stk.size() – del)即从”10″末尾删除1个字符得到”1″。正确所以最终结果是”1″。前导零处理result”1″find_first_not_of(‘0’)返回0substr(0)得到”1″。正确。 所以我的初始分析在”10″例子上绕晕了。算法是正确的。前导零处理是针对像num”100200″, k1得到”10200″或者num”100″, k1得到”10″再末尾删除得”1″这种情况。但更极端的是num”100″, k2算法可能得到”10″再末尾删除得””需要返回”0″。所以前导零处理模块if (nonZeroPos string::npos) return “0”;是安全的。关键心得在实现时务必用多个边缘用例测试特别是全零、删除后为空、删除后产生前导零的情况。”10″, k1就是一个很好的测试用例。4. 核心解法二基于字符串的直接操作解法对于习惯字符串操作或者想更直观理解“删除”过程的同学可以直接在字符串上进行操作。思路与数组/栈解法完全一致只是把stk换成了一个字符串result。4.1 字符串解法的实现与对比#include iostream #include string using namespace std; string removeKdigits(string num, int k) { string result; // 用字符串直接作为结果栈 int del k; for (char digit : num) { while (!result.empty() result.back() digit del 0) { result.pop_back(); // 弹出末尾字符 del--; } result.push_back(digit); // 当前字符加入结果 } // 如果还有删除次数从末尾删除 if (del 0) { result.resize(result.size() - del); } // 去除前导零 size_t nonZeroPos result.find_first_not_of(‘0’); if (nonZeroPos string::npos) { return “0”; } return result.substr(nonZeroPos); }与数组解法的异同本质相同算法逻辑、时间复杂度O(n)、空间复杂度O(n)完全一致。操作对象数组解法使用vectorchar字符串解法使用string。在C中string也提供了back(),pop_back(),push_back()方法使用起来同样方便。细微差别vector在语义上更强调“容器”而string更强调“字符序列”。对于这道题两者均可。部分选手可能觉得string更贴近题意操作数字字符串。4.2 字符串操作的性能与注意事项直接使用string作为栈代码更简洁也避免了容器类型转换。但需要注意resize与erase的选择在删除末尾多余字符时我们使用了result.resize(result.size() – del)。这比使用result.erase(result.end() – del, result.end())在语法上稍简洁一些性能上区别不大。内存连续性string和vector都保证元素在内存中连续存储因此通过索引或迭代器访问速度很快。这也是我们能用它们模拟栈的基础。find_first_not_of的效率去除前导零时find_first_not_of(‘0’)需要遍历字符串直到找到第一个非 ‘0’ 字符或到达末尾。在最坏情况结果全是’0’下它会遍历整个结果字符串。但这部分开销是 O(n)且是必要的不影响整体 O(n) 的复杂度。5. 深度优先搜索DFS思路的探讨与局限性题目相关的热词中出现了“DFS搜索”这提示我们也可以从搜索的角度思考。虽然对于本题的数据规模长度可能上千DFS不是可行解但理解其思路有助于加深对问题本质的认识。5.1 DFS 解法的抽象模型我们可以把问题转化为从一个长度为n的字符串中选择一个长度为n-k的子序列保持原顺序使得其字典序最大。 DFS 函数可以设计为dfs(idx, selectedCount, currentPath)其中idx当前决策到原字符串的第几个位置。selectedCount已经选择了多少个字符放入currentPath。currentPath当前已选择的字符构成的字符串。在每一层我们有两种选择选择当前字符如果selectedCount n-k可以将num[idx]加入currentPath然后递归到idx1, selectedCount1。不选择当前字符直接递归到idx1, selectedCount。递归终止条件当idx n时如果selectedCount n-k则用currentPath更新最终答案保留字典序最大的。5.2 DFS 的局限性与优化启示这种朴素的 DFS 时间复杂度是指数级的 O(2^n)对于 n 稍大就完全不可行。但它清晰地揭示了问题的组合本质。为什么贪心有效贪心算法可以看作是对这个巨大搜索空间进行“剪枝”后的高效搜索。它利用了“高位数字更重要”这一性质在每一步都做出了局部最优选择从而避免了探索绝大多数无效路径。这提醒我们面对组合优化问题时先分析问题是否具有贪心选择性质和最优子结构往往能化指数复杂度为线性复杂度。6. 常见错误与调试技巧实录在实际编码和调试过程中以下几个错误非常高频错误1贪心条件写反错误代码while (!stk.empty() stk.back() digit del 0)这是求最小数的条件。症状对于求最大数的题目得到的结果会偏小。检查方法用简单用例测试如num”12″, k1。正确结果应为”2″。如果得到”1″就是条件写反了。错误2忽略删除次数未用完的情况错误代码遍历结束后直接返回结果没有if (del 0)的处理段。症状对于单调递减或平缓的输入如”4321″, k2返回的结果长度不对会比预期长。检查方法测试num”4321″, k2。正确结果应为”43″。如果得到”4321″就是漏了这一步。错误3前导零处理不当错误代码没有去除前导零或者去除后对于空结果没有返回”0″。症状对于num”10020″, k1可能返回”0020″或””而不是”20″或”0″。检查方法必须测试包含多个0的用例特别是删除后可能全零的情况如num”1000″, k1正确结果应为”100″num”1000″, k3正确结果应为”1″num”10″, k1正确结果应为”1″。错误4使用int或long long存储中间结果症状当输入字符串很长时转换成的整数会溢出导致错误。规避方法始终牢记题目可能涉及大数全程使用字符串或数组进行比较和存储。调试技巧打印中间状态在贪心循环中每步操作后打印出当前的栈stk或result内容和剩余删除次数del可以非常清晰地看到算法是如何一步步构建结果的。设计小规模测试集包含递增序列、递减序列、有峰有谷的序列、包含0的序列等多种情况。例如(“1234”, 2),(“4321”, 2),(“1432219”, 3),(“10200”, 1),(“10”, 2),(“100”, 1)。边界测试k0应返回原串k等于字符串长度-1应返回最大的单个字符字符串全为相同数字等。7. 算法扩展与变式思考掌握了本题的核心解法后可以思考一些相关的变式问题这有助于融会贯通求移除K位后的最小数这就是LeetCode上经典的“移掉K位数字”问题。只需将贪心条件中的stk.back() digit改为stk.back() digit即可。同样需要注意前导零处理。至多移除K位求最大/最小数题目要求可能变成“最多移除K位”此时如果提前用完删除次数固然好如果用不完保留原样即可。我们的算法框架依然适用只需调整循环条件和末尾处理逻辑。在限制条件下选择子序列这类问题可以抽象为“从一个序列中按原序选出一个定长子序列使其满足某种最优性质”。除了字典序最大/最小还可能是和最大、满足某种单调性等。解题思路往往是贪心或动态规划。我个人在反复练习这类题目后最大的体会是贪心算法的核心在于“决策的不可撤销性”和“局部最优的全局有效性”。在这道题中我们一旦决定将一个数字放入结果栈或字符串在后续的决策中就不会再回头考虑替换它除非它被后面更大的数字“顶替”。这种“栈”的结构完美地契合了这种“后悔”机制——只有当后面遇到更好的才把之前不够好的替换掉。而最后处理剩余删除次数的步骤则是应对那些“一直没有遇到更好选择”情况的保底策略。把这种模型理解透彻很多类似的字符串处理、序列选择问题都能迎刃而解。最后再分享一个编码习惯在写这类逻辑时不妨先写注释把算法步骤列出来然后再填充代码并立刻用想到的极端用例在脑子里跑一遍能提前避免很多低级错误。