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 possi
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\uff1f 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:\n```\nstring removeKdigits(string num, int k) {\n        while (k > 0) {\n            int n = num.size();\n            int i = 0;\n            while (i+1<n && num[i]<=num[i+1])  i++;\n            num.erase(i, 1);\n            k--;\n        }\n        // trim leading zeros\n        int s = 0;\n        while (s<(int)num.size()-1 && num[s]=='0')  s++;\n        num.erase(0, s);\n        \n        return num=="" ? "0" : num;\n    }\n```\nThe above algorithm is a bit inefficient because it frequently remove a particular element from a string and has complexity O(k*n).\n\nOne 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.\n```\nstring removeKdigits(string num, int k) {\n        string res;\n        int keep = num.size() - k;\n        for (int i=0; i<num.size(); i++) {\n            while (res.size()>0 && res.back()>num[i] && k>0) {\n                res.pop_back();\n                k--;\n            }\n            res.push_back(num[i]);\n        }\n        res.erase(keep, string::npos);\n        \n        // trim leading zeros\n        int s = 0;\n        while (s<(int)res.size()-1 && res[s]=='0')  s++;\n        res.erase(0, s);\n        \n        return res=="" ? "0" : res;\n    }\n```
[]