A greedy method O(n) time and O(1) space


  • 0
    N

    I erase the first maximum every time. I used cur to record the position. So the time complexity is O(n).

    class Solution {
    public:
        string removeKdigits(string num, int k) {
            if (num.size() <= k)
                return "0";
            string res = num;
            int cur = 0;
            for (int i=0; i<k; i++) {
                int cut = false;
                for (int j=cur; j<res.size()-1; j++)
                    if (res[j] > res[j+1]) {
                        res.erase(res.begin()+j);
                        cut = true;
                        cur = j;
                        break;
                    }
                if (cur != 0)
                    cur--;
                if (!cut)
                    res.erase(res.end()-1);
            }
            while (res[0] == '0')
                res = res.substr(1);
            if (res == "")
                res = "0";
            return res;
        }
    };
    

Log in to reply
 

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