problem:402. 移掉 K 位数字

思路：对于每个数字，如果该数字小于栈顶元素，我们就不断地弹出栈顶元素，直到

• 栈为空
• 或者新的栈顶元素不大于当前数字
• 或者我们已经删除了 kkk 位数字

Accode:

class Solution {
public:
    string removeKdigits(string num, int k) {
        if(k>=num.size()) return "0";
        vector<char> sta;
        for(int i=0;i<num.size();i++){
            // if(already_remove_cnt>=k) continue;
            while(sta.size() && sta.back()>num[i] && k){
                sta.pop_back();
                k--;
            }
            sta.push_back(num[i]);
        }
        while(k>0){
            sta.pop_back();
            k--;
        }
        string ans = "";
        bool allZero = true;
        for(int i=0;i<sta.size();i++){
            if(allZero && sta[i]=='0'){
                continue;
            }
            allZero = false;
            ans+=sta[i];
        }
        return ans==""?"0":ans;

    }
};

时间复杂度： $o(n)$