0402. Remove K Digits¶
Given string num representing a non-negative integer num, and an integer k, return the smallest possible integer after removing k digits from num.
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.
Constraints:
1 <= k <= num.length <= 105numconsists of only digits.numdoes not have any leading zeros except for the zero itself.
Analysis¶
This question asks to remove arbitrary k digits from num to form the smallest string. We can drill down the problem from a simple question like how to remove one digit from the string. For example, given 12321 we will remove 3 from the string because 1221 should be the smallest string. Given 123291 we should remove 3 instead of 9 because 12321 is bigger than 12291. From here, we realize that we cannot just remove the largest element but we should check from left to right to minimize the preceding elements that are the smallest. In another word, we should maintain the smallest possible non-decreasing string, and it sounds like a monotonic stack algorithm.
Since we are using a string, we can mimic the string as a stack: there is a pop_back in string we can use.
- Time: O(n)
- Space: O(n) for the stack
Code¶
class Solution {
public:
string removeKdigits(string a, int k) {
string res;
int n = a.size(), keep = n - k;
for (char c : a) {
// note: this is a while loop to compare all the previous
// smaller char, because there could be multiple smaller char in front of i
while (k && !res.empty() && res.back() > c) {
res.pop_back();
--k;
}
res += c;
}
res.resize(keep); // keep the smallest first n - k chars
// remove the leading zeros
while (!res.empty() && res[0] == '0') {
res.erase(res.begin());
}
return res.empty() ? "0" : res;
}
};