C++_O(n)_Accepted_23ms_35.48%


  • 0

    (Actually I think my method is not O(n) time complexity.... :-) )
    I think this problem is similar like a problem which requests you make a string sorted without disorganizing the original orders of chars, by deleting k chars.

    For this problem, we should notice that:

    1. If we set an integer RES to store our final result, then there may be overflow for integer, even if you use long or long long;

    2. the input like : "01" 1, if the final result is (int) zero, then our output may be an empty string("");

    3. For input like"111222333" or "1111111", we may find that finally the k is not equal to zero, so we should double check after we finish the stack.push() procedures, which is pop the elements in the stack until k = 0;

     class Solution {
     public:
     string removeKdigits(string num, int k) {
        int n = num.size();
        stack<int> stk;
        int i = 0;
        while(i < n){
            int tmp  = num[i] - '0';
            if(stk.empty() || k <= 0){stk.push(tmp);}
            else{
                while(!stk.empty() && stk.top() > tmp && k > 0){
                        stk.pop();
                        k--;
                }
                stk.push(tmp);
            }
            i++;
        }
        
        while(k > 0){
            stk.pop();
            k--;
        }
        
        string res = "";
        while(!stk.empty()){
            res = to_string(stk.top())  + res;
            stk.pop();
        }
        
        i = 0;
        while(res[i] == '0'){i++;}
        res = res.substr(i);
        return res == "" ? "0" : res;
    }  };

Log in to reply
 

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