给你一个以字符串表示的非负整数 num 和一个整数 k ,移除这个数中的 k 位数字,使得剩下的数字最小。请你以字符串形式返回这个最小的数字。
示例 1 :
1 2 3
| 输入:num = "1432219", k = 3 输出:"1219" 解释:移除掉三个数字 4, 3, 和 2 形成一个新的最小的数字 1219 。
|
示例 2 :
1 2 3
| 输入:num = "10200", k = 1 输出:"200" 解释:移掉首位的 1 剩下的数字为 200. 注意输出不能有任何前导零。
|
示例 3 :
1 2 3
| 输入:num = "10", k = 2 输出:"0" 解释:从原数字移除所有的数字,剩余为空就是 0 。
|
解题思路
核心思路是单调栈 + 贪心算法,通过维护一个递增的栈来确保剩余数字最小,同时控制移除的数字数量不超过 k:
- 单调栈逻辑:
- 遍历字符串中的每个数字,对于当前数字
c:
- 若栈不为空,且栈顶数字大于
c,且仍有可移除的次数(k > 0),则弹出栈顶数字(移除该数字可使结果更小),同时 k--;
- 将当前数字
c 压入栈。
- 处理剩余可移除次数:
- 若遍历结束后
k 仍大于 0(说明剩余数字是递增的),则从栈尾移除 k 个数字。
- 清理前导零和空字符串:
- 移除栈中开头的所有 '0'(避免前导零);
- 若栈为空,返回 "0",否则返回栈中字符组成的字符串。
代码实现
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41
| #include <string> #include <vector> using namespace std;
class Solution { public: string removeKdigits(string num, int k) { vector<char> stack; // 用vector模拟栈,便于处理 for (char c : num) { // 栈非空,栈顶数字大于当前数字,且还有可移除次数 while (!stack.empty() && k > 0 && stack.back() > c) { stack.pop_back(); // 移除栈顶数字 k--; } stack.push_back(c); // 当前数字入栈 } // 若还有剩余可移除次数,从栈尾移除 while (k > 0 && !stack.empty()) { stack.pop_back(); k--; } // 移除前导零 int start = 0; while (start < stack.size() && stack[start] == '0') { start++; } // 构建结果 string result; for (int i = start; i < stack.size(); ++i) { result += stack[i]; } // 若结果为空,返回"0",否则返回结果 return result.empty() ? "0" : result; } };
|