0402. Remove K Digits ===================== 题目信息 -------- :题号: 0402 :难度: Medium :主题: 十进制字符串、删除字符、最小数值、前导零 :原题: `LeetCode 0402 `_ :重点: 必须恰好删除 ``k`` 位、剩余数字保持原顺序、结果去除前导零、空结果表示为 ``0`` 题目重述 -------- 给定表示非负整数的十进制字符串 ``num`` 和整数 ``k``,从字符串中恰好删除 ``k`` 个数字字符,使剩余字符按原有相对顺序组成的整数尽可能小,并返回该整数的字符串表示。 ``num`` 的长度位于 ``[1, 10^5]``,只包含数字,除字符串 ``"0"`` 外不会以 ``0`` 开头;``k`` 位于 ``[0, num.length]``。结果不能含无意义的前导零;若删除后没有字符,或者剩余数值为零,必须返回 ``"0"``。 自建示例 -------- 删除较大的高位数字: .. code-block:: text 输入:num = "7650281",k = 3 输出:"281" 解释:删除 7、6、5 后得到 0281,去除前导零后为 281;不存在更小的合法结果。 剩余字符全部表示零: .. code-block:: text 输入:num = "10020",k = 2 输出:"0" 解释:删除 1 和 2 后剩下 000,规范化结果必须写成单个字符 "0"。 单调栈保留尽可能小的高位 -------------------------- 从左到右构造结果。若当前数字比栈顶小,栈顶作为更高位就会使结果变大;只要还有删除额度,就弹出这样的栈顶,再放入当前数字。弹栈停止后,栈内前缀已经是当前扫描范围能得到的最小前缀。 扫描结束仍有删除额度时,只能从末尾删除,因为前面的字符已经按贪心确定;最后去掉所有前导零,空串或全零结果统一写为 ``"0"``。这保证恰好删除 ``k`` 位,而不是只删除有利于变小的位。 C++ 实现 -------- .. code-block:: cpp class Solution { public: std::string removeKdigits(std::string num, int k) { std::string stack; for (char digit : num) { while (k > 0 && !stack.empty() && stack.back() > digit) { stack.pop_back(); --k; } stack.push_back(digit); } while (k > 0 && !stack.empty()) { stack.pop_back(); --k; } int first = 0; while (first < static_cast(stack.size()) && stack[first] == '0') { ++first; } std::string result = stack.substr(first); return result.empty() ? "0" : result; } }; 代码分析 -------- 在相邻的下降处优先删除左侧较大的数字,是数值比较中最重要的高位决策;每个字符最多入栈、出栈一次,删除额度始终准确递减。先完成删除、再规范化前导零,避免把零误当成可以少删的字符。时间复杂度为 ``O(n)``,额外空间为 ``O(n)``。