删除 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,单调栈依次弹出 4、4、3。solution("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 可见样例;服务端提交会运行可见样例和隐藏测试。
默认展示公开样例。点击「运行样例」后会在这里显示实际输出;点击「提交评测」会进入隐藏测试。
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"。函数应当快速返回,不进入栈逻辑。