402. 移掉 K 位数字 #
链接 #
题目 #
给你一个以字符串表示的非负整数 num 和一个整数 k ，移除这个数中的 k 位数字，使得剩下的数字最小。请你以字符串形式返回这个最小的数字。
示例 1 ：
输入：num = "1432219", k = 3 输出："1219" 解释：移除掉三个数字 4, 3, 和 2 形成一个新的最小的数字 1219 。
示例 2 ：
输入：num = "10200", k = 1 输出："200" 解释：移掉首位的 1 剩下的数字为 200. 注意输出不能有任何前导零。
示例 3 ：
输入：num = "10", k = 2 输出："0" 解释：从原数字移除所有的数字，剩余为空就是 0 。
提示：
1 <= k <= num.length <= 105num仅由若干位数字（0 - 9）组成- 除了 0 本身之外，
num不含任何前导零
解答 #
class Solution {
public:
string removeKdigits(string num, int k) {
stack<int> incrpos;
int n = num.size();
int i = 0;
map<int, bool> removeidx;
do {
// 能增长的统统入栈，从栈尾部开删，删 k 个
while(i < n && (incrpos.empty() || num[incrpos.top()] <= num[i])) {
incrpos.push(i++);
}
auto outidx = incrpos.top(); incrpos.pop();
removeidx[outidx] = true;
k--;
} while(k > 0 && (!incrpos.empty() || i < n));
// 上面就是核心代码，下面都是擦屁股的
// 删完了，返回 0
if(removeidx.size() == num.size()) {
return "0";
}
// 处理前导 0
bool prezero = true;
string out;
for(int i = 0; i < n; i++ ) {
if(removeidx[i] == true || num[i] == '0' && prezero) {
continue;
}
if(num[i] != '0') {
prezero = false;
}
out.push_back(num[i]);
}
return prezero ? "0": out;
}
};