1. 问题背景与需求分析1321删数问题是一个经典的贪心算法练习题主要考察选手对数字特性和贪心策略的理解。题目通常给出一个由数字组成的字符串和一个正整数k要求从中删除k个数字后使剩下的数字组成的新数最小。这个问题在实际中有很多应用场景比如优化存储空间时选择删除哪些冗余数据金融交易中最小化手续费的计算资源分配时如何做出最优取舍我第一次接触这个问题是在准备NOIP比赛时当时就被它简洁描述背后隐藏的巧妙解法所吸引。经过多次练习和教学实践我总结出了一套系统的解题思路和常见错误防范方法。2. 算法思路解析2.1 贪心算法选择解决这个问题的核心在于理解贪心算法的适用性。我们需要在每一步做出局部最优选择最终达到全局最优解。具体到这个题目从左到右遍历数字字符串当发现当前数字比下一个数字大时删除当前数字重复这个过程直到删除k个数字这种策略之所以有效是因为数字的高位对数值大小的影响更大。比如数字132删除3得到的12比删除1得到的32更小。2.2 数据结构选择为了实现这个算法我们需要选择合适的数据结构。经过实践比较我推荐使用栈Stack来实现栈可以帮助我们方便地比较当前元素和前一个元素栈的LIFO特性正好符合我们需要回溯检查的需求栈操作的时间复杂度为O(1)整体算法可以达到O(n)的时间复杂度以下是使用栈的伪代码框架stack [] for digit in num_str: while k 0 and stack and stack[-1] digit: stack.pop() k - 1 stack.append(digit)3. 完整实现与代码解析3.1 Python实现代码def removeKDigits(num: str, k: int) - str: stack [] for digit in num: while k 0 and stack and stack[-1] digit: stack.pop() k - 1 stack.append(digit) # 如果还有剩余的k需要删除 if k 0: stack stack[:-k] # 处理前导零 result .join(stack).lstrip(0) return result if result else 03.2 关键点解析循环条件内层while循环的三个条件缺一不可k 0确保不会删除超过k个数字stack确保栈不为空stack[-1] digit当前数字比下一个数字大时才删除剩余k处理如果遍历完字符串后k仍然大于0说明数字是递增的直接从末尾删除剩余k个数字前导零处理使用lstrip(0)去除前导零同时注意全零情况要返回04. 边界情况与测试用例4.1 常见边界情况全部数字相同11111, k2 → 111递增序列12345, k2 → 123递减序列54321, k2 → 321包含前导零100200, k1 → 00200 → 200删除所有数字123, k3 → 04.2 测试用例设计test_cases [ (1432219, 3, 1219), (10200, 1, 200), (10, 2, 0), (1234567890, 9, 0), (4321, 2, 21), (100, 1, 0), (112, 1, 11) ]5. 算法优化与变种5.1 时间复杂度分析原始算法的时间复杂度是O(n)因为每个数字最多入栈和出栈一次。空间复杂度也是O(n)用于存储栈。5.2 实际应用中的优化提前终止当k减到0时可以直接将剩余数字加入结果无需继续比较双端队列可以使用collections.deque代替list实现的栈在某些情况下性能更好字符串操作对于小规模数据直接操作字符串可能更简单直观5.3 问题变种删除数字使结果最大只需将比较条件改为stack[-1] digit删除特定数字如删除所有0或特定模式的数字带权重的删数每个数字有不同的删除成本需要综合考虑6. 常见错误与调试技巧6.1 新手常见错误忽略前导零没有正确处理像0200这样的情况剩余k处理不当忘记处理遍历结束后k0的情况边界条件遗漏没有考虑k0或k字符串长度的情况数据类型混淆将数字字符串当作数值处理导致前导零丢失6.2 调试建议打印中间结果在循环中加入print语句观察栈的变化小规模测试先用简单例子如123, k1手动验证逐步增加复杂度从简单情况开始逐步增加数字长度和k值使用断言在代码中添加assert检查不变量重要提示在处理字符串数字时始终记住保持字符串类型直到最后避免过早转换为整数导致前导零丢失。7. 教学实践心得在教学过程中我发现学生最容易困惑的是为什么贪心算法在这里适用。我通常用以下方式来解释想象数字字符串是一座山峰我们要删除的是山峰而不是山谷。因为山峰局部最大值的存在会让整体数值变大而我们要的是尽可能小的数。所以应该优先删除这些山峰。另一个实用的教学技巧是让学生手动模拟算法过程。例如对于1432219, k31 → [1]4 (14) → [1,4]3 (43,删除4) → [1,3], k22 (32,删除3) → [1,2], k12 → [1,2,2]1 (21,删除2) → [1,2,1], k09 → [1,2,1,9] 结果1219这种逐步演示能帮助学生直观理解算法的工作原理。