# 402. Remove K Digits

Given a non-negative integer  num  represented as a string, remove  k  digits from the number so that the new number is the smallest possible.

Note:

• The length of  num  is less than 10002 and will be ≥  k.
• The given  num  does not contain any leading zero.

Example 1:

``````Input: num = "1432219", k = 3
Output: "1219"
Explanation: Remove the three digits 4, 3, and 2 to form the new number 1219 which is the smallest.
``````

Example 2:

``````Input: num = "10200", k = 1
Output: "200"
Explanation: Remove the leading 1 and the number is 200. Note that the output must not contain leading zeroes.
``````

Example 3:

``````Input: num = "10", k = 2
Output: "0"
Explanation: Remove all the digits from the number and it is left with nothing which is 0.
``````

``````class Solution {
public:
string removeKdigits(string num, int k) {
string res = "";
int n = num.size(), keep = n - k;
for (char c : num) {
while (k && res.size() && res.back() > c) {
res.pop_back();
--k;
}
res.push_back(c);
}
res.resize(keep);
while (!res.empty() && res[0] == '0') res.erase(res.begin());
return res.empty() ? "0" : res;
}
};
``````

``````class Solution {
public:
string removeKdigits(string num, int k) {
string res;
int n = num.size(), keep = n - k;
for (char c : num) {
while (k && res.size() && res.back() > c) {
res.pop_back();
--k;
}
if (res.size() || c != '0') res.push_back(c);
}
while (res.size() && k--) res.pop_back();
return res.empty() ? "0" : res;
}
};
``````

Github 同步地址：

https://github.com/grandyang/leetcode/issues/402

Create Maximum Number

Remove Duplicate Letters

https://leetcode.com/problems/remove-k-digits/

https://leetcode.com/problems/remove-k-digits/discuss/88708/Straightforward-Java-Solution-Using-Stack

https://leetcode.com/problems/remove-k-digits/discuss/88660/A-greedy-method-using-stack-O(n)-time-and-O(n)-space

LeetCode All in One 题目讲解汇总(持续更新中…)

 微信打赏 Venmo 打赏
（欢迎加入博主的知识星球，博主将及时答疑解惑，并分享刷题经验与总结，试运营期间前五十位可享受半价优惠～）

×

Help us with donation