← 返回编程题库
coding-removing-k-digits-monotonic中等免费版2000ms未尝试

删除 K 位数字 — 最小结果

Removing K Digits — Smallest Result

开始编码

行情工具吐出一个用字符串表示的非负整数 num,分析师想知道:恰好删掉 k 位数字、保持其余数字的相对顺序后,能得到的最小值是多少。这就是 LeetCode 402 的经典题,本题把它包装成一个微结构数据清洗任务——把 num 看作一段序列号、时间戳或订单 id,前位数字主导量级,团队希望得到长度为 len(num) - k字典序最小子序列

请实现 solution(num: str, k: int) -> str。规则:(1)必须恰好删除 k 位,不多不少;(2)保留下来的数字必须保持原相对顺序(是子序列,不是子集);(3)当 k == len(num) 时返回 "0";(4)若保留下来的子序列有前导零,需剥掉;若剥完为空,返回 "0"

示例solution("1432219", 3) 返回 "1219"——经典 LC402 例 1,单调栈依次弹出 443solution("10200", 1) 返回 "200"——删掉首位 1"0200",必须把前导零去掉成 "200",这是最常见的边界陷阱。solution("10", 2) 返回 "0"——k 等于长度,全删完,按约定返回 "0"

关键技巧是贪心 + 单调栈:从左到右扫,每当栈顶严格大于当前数字且还有删除额度,就弹出栈顶。每次弹出都把一个高位的较大数字换成更靠右的较小数字,结果严格变小。扫完后若 k 还有剩,栈里已经是非递减序列,直接从尾部弹掉最后 k 个即可。最后再去掉前导零。整体 O(n) 时间、O(n) 空间——每位数字最多入栈、出栈各一次。这个套路(用单调栈构造字典序最小子序列)也出现在「去重保最小」「最小子序列」等题里,在压缩冗余订单簿更新消息这类微结构代码中也很实用。

约束条件

  • 1 ≤ len(num) ≤ 10000
  • 0 ≤ k ≤ len(num)
  • num 是不含前导零的非负整数字符串(唯一例外是 num == "0" 这种单字符 0 的情况)
  • 若 k == len(num),返回 "0";若删除后为空或全为零,返回 "0"
  • 结果以字符串精确比较(exact)

样例

Case 1 · classic LC402 — remove three digits

输入: ["1432219",3]

期望: "1219"

经典 LC402 例 1。从左到右扫描,遇到 4>3 弹出 4(剩 k=2),遇到 4>2 弹出原来的 4 后又弹出 3(剩 k=1),... 最终单调栈得到 1219,是删除 3 位后字典序最小的结果。

Case 2 · leading-zero trimming (LC402 example 2)

输入: ["10200",1]

期望: "200"

弹出首位 1 后剩下 "0200",必须去掉前导零得到 "200"。这一步去前导零是 LC402 最常见的边界陷阱。

Case 3 · k equals length — return "0"

输入: ["10",2]

期望: "0"

k 等于字符串长度时全部删完,按约定返回 "0"。函数应当快速返回,不进入栈逻辑。

最近提交

还没有提交记录。

编码区

实现 solution(...)。本地运行当前支持 Python 可见样例;服务端提交会运行可见样例和隐藏测试。

加载编辑器...
计时0:00

默认展示公开样例。点击「运行样例」后会在这里显示实际输出;点击「提交评测」会进入隐藏测试。

Case 1 · classic LC402 — remove three digits

输入: ["1432219",3]

期望: "1219"

经典 LC402 例 1。从左到右扫描,遇到 4>3 弹出 4(剩 k=2),遇到 4>2 弹出原来的 4 后又弹出 3(剩 k=1),... 最终单调栈得到 1219,是删除 3 位后字典序最小的结果。

Case 2 · leading-zero trimming (LC402 example 2)

输入: ["10200",1]

期望: "200"

弹出首位 1 后剩下 "0200",必须去掉前导零得到 "200"。这一步去前导零是 LC402 最常见的边界陷阱。

Case 3 · k equals length — return "0"

输入: ["10",2]

期望: "0"

k 等于字符串长度时全部删完,按约定返回 "0"。函数应当快速返回,不进入栈逻辑。