Two algorithms with detailed explaination

• The first algorithm is straight-forward. Let's think about the simplest case: how to remove 1 digit from the number so that the new number is the smallest possible？ Well, one can simply scan from left to right, and remove the first "peak" digit; the peak digit is larger than its right neighbor. One can repeat this procedure k times, and obtain the first algorithm:

``````string removeKdigits(string num, int k) {
while (k > 0) {
int n = num.size();
int i = 0;
while (i+1<n && num[i]<=num[i+1])  i++;
num.erase(i, 1);
k--;
}
int s = 0;
while (s<(int)num.size()-1 && num[s]=='0')  s++;
num.erase(0, s);

return num=="" ? "0" : num;
}
``````

The above algorithm is a bit inefficient because it frequently remove a particular element from a string and has complexity O(k*n).

One can simulate the above procedure by using a stack, and obtain a O(n) algorithm. Note, when the result stack (i.e. res) pop a digit, it is equivalent as remove that "peak" digit.

``````string removeKdigits(string num, int k) {
string res;
int keep = num.size() - k;
for (int i=0; i<num.size(); i++) {
while (res.size()>0 && res.back()>num[i] && k>0) {
res.pop_back();
k--;
}
res.push_back(num[i]);
}
res.erase(keep, string::npos);

int s = 0;
while (s<(int)res.size()-1 && res[s]=='0')  s++;
res.erase(0, s);

return res=="" ? "0" : res;
}
``````

• Brief and clear explanation, thanks!

• thanks a lot！！

• Nice solution, but would you mind share some thinking processes of how to come up with the solution to look for the peak value. When I first came across this problem, I go into a totally different solution which turns out to be wrong.

• This post is deleted!

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.