Two algorithms with detailed explaination


  • 25
    P

    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--;
            }
            // trim leading zeros
            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);
            
            // trim leading zeros
            int s = 0;
            while (s<(int)res.size()-1 && res[s]=='0')  s++;
            res.erase(0, s);
            
            return res=="" ? "0" : res;
        }
    

  • 0
    S

    Brief and clear explanation, thanks!


  • 0
    S

    thanks a lot!!


  • 2

    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.


  • 0
    A
    This post is deleted!

Log in to reply
 

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