3ms C++ with Deque


  • 0
    S
    class Solution {
    public:
        string removeKdigits(string num, int k) {
            deque<char> dq;
            int i = 0, cnt = 0;
            for (; i < num.size(); i++) {
                while (!dq.empty() && num[i] < dq.front() && cnt < k) {
                    dq.pop_front();
                    cnt++;
                }
                if (cnt == k) break;
                dq.push_front(num[i]);
            }
            while (cnt++ < k && !dq.empty()) dq.pop_front();
            
            // drop leading '0'
            while (!dq.empty() && dq.back() == '0') dq.pop_back();
            while (dq.empty() && num[i] == '0') i++;
            // drop leading '0'
            
            string ret;
            while (!dq.empty()) {
                ret.push_back(dq.back());
                dq.pop_back();
            }
            ret += num.substr(i, num.size() - i);
            return ret.size() ?ret :"0";
        }
    };
    

    Traits of deque can be changed to the traits of string itself, but when dropping the leading zeros, string is slower.


Log in to reply
 

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