当前位置：首页 > news >正文

贪心算法实现删除重复数字后的最大数字

news 2026/8/10 4:44:52

1. 问题背景与需求分析

"删除重复数字后的最大数字"是一个经典的字符串处理问题，常见于编程面试和算法竞赛中。给定一个由数字组成的字符串，我们需要从中删除k个重复的数字，使得剩下的数字组成的新字符串是所有可能结果中数值最大的那个。

这个问题看似简单，但实际涉及多个关键点：

如何定义"重复数字"（连续重复还是全局重复）
删除策略对最终结果的影响
如何保证在删除操作后得到的数字最大

在实际应用中，这类算法可以用于：

数据清洗中的冗余信息处理
金融交易中的订单号优化
游戏开发中的资源ID管理

2. 算法思路解析

2.1 贪心算法选择

经过多次实践验证，贪心算法是解决此类问题的最佳选择。其核心思想是：在每一步选择中都采取当前最优的选择，从而希望导致全局最优的结果。

具体到这个题目：

我们需要维护一个结果栈
遍历原字符串中的每个数字
对于当前数字，如果它比栈顶数字大，且我们还可以删除数字（k>0），且栈顶数字在当前数字后面不会再出现，那么就弹出栈顶数字
将当前数字压入栈中
最后如果还有剩余的删除次数，从栈尾部删除相应数量的数字

2.2 关键实现细节

def removeKdigits(num: str, k: int) -> str: stack = [] remain = len(num) - k for digit in num: while k and stack and stack[-1] < digit: stack.pop() k -= 1 stack.append(digit) return ''.join(stack[:remain]).lstrip('0') or '0'

这个实现有几个关键点需要注意：

使用列表模拟栈结构，提高操作效率
在删除时确保不会过度删除（remain变量的控制）
处理前导零的特殊情况
边界条件处理（当所有数字都被删除时返回"0"）

3. 复杂度分析与优化

3.1 时间复杂度

该算法的时间复杂度为O(n)，其中n是输入字符串的长度。这是因为：

每个数字最多被压入和弹出栈各一次
遍历整个字符串只需要一次

3.2 空间复杂度

空间复杂度也是O(n)，主要用于存储结果栈。在最坏情况下（不需要删除任何数字），栈的大小等于输入字符串长度。

3.3 实际优化技巧

在实际编码面试中，可以注意以下优化点：

提前判断特殊情况：如果k >= len(num)，直接返回"0"
使用双端队列代替列表，在某些语言中可能更高效
在字符串拼接时，使用join而不是+=操作

4. 常见错误与调试技巧

4.1 典型错误案例

错误处理前导零：
- 输入："10200", k=1
- 错误输出："0200"
- 正确输出："2000"
删除次数未用完：
- 输入："12345", k=2
- 错误输出："12345"
- 正确输出："345"
边界条件处理：
- 输入："10", k=2
- 错误输出：""
- 正确输出："0"

4.2 调试方法

使用小规模测试用例手动模拟算法执行过程
打印关键变量（栈内容、当前数字、剩余k值）的变化
特别注意循环终止条件和边界情况
对于困难案例，可以分步骤验证算法决策的正确性

5. 变种问题与扩展思考

5.1 相关变种问题

删除重复数字后的最小数字
删除任意k个数字后的最小数字
保留k个重复数字的最大数字
带有权重约束的数字删除问题

5.2 实际应用扩展

在真实业务场景中，这类算法可以应用于：

优惠码生成系统：确保生成的优惠码没有不必要的重复
日志压缩：去除重复的日志条目
数据仓库优化：消除冗余数据记录

5.3 算法选择思考

为什么贪心算法适用于这个问题？因为这个问题具有"最优子结构"特性：

局部最优解能导致全局最优解
无后效性：当前决策不会影响后续决策
可以通过数学归纳法证明其正确性

6. 不同语言的实现差异

6.1 Java实现要点

public String removeKdigits(String num, int k) { Deque<Character> stack = new ArrayDeque<>(); for (char digit : num.toCharArray()) { while (k > 0 && !stack.isEmpty() && stack.peekLast() < digit) { stack.pollLast(); k--; } stack.offerLast(digit); } while (k-- > 0) stack.pollLast(); StringBuilder ret = new StringBuilder(); boolean leadingZero = true; for (char digit : stack) { if (leadingZero && digit == '0') continue; leadingZero = false; ret.append(digit); } return ret.length() == 0 ? "0" : ret.toString(); }

Java实现需要注意：

使用Deque接口而不是Stack类（性能更好）
显式处理前导零
StringBuilder的合理使用

6.2 C++实现特点

string removeKdigits(string num, int k) { string result; for (char c : num) { while (k > 0 && !result.empty() && result.back() < c) { result.pop_back(); k--; } result.push_back(c); } result.resize(result.size() - k); size_t pos = result.find_first_not_of('0'); return pos == string::npos ? "0" : result.substr(pos); }

C++实现的特点：