This is a typical monotonic queue question. Share my c++ solution


  • 2

    It is kinds of greedy idea. As long as we have enough elements, we should pop_back the rear element of string res, which is larger than current element num[i]. It is because we can guarantee that the new res after push num[i] is smaller than before.

        string removeKdigits(string num, int k) {
            string res="";
            if(num.size()==k)
                return "0";
            for(int i=0;i<num.size();i++){
                while(!res.empty()&&res.back()>num[i]&&k>0){
                    res.pop_back();
                    k--;
                }
                res.push_back(num[i]);
            }
            auto pos=res.find_first_not_of('0');
            if(pos==string::npos)
                return "0";
            return res.substr(pos,num.size()-k);
        }
    

Log in to reply
 

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