402.移掉K位数字

402.移掉 K 位数字

题目描述：

给出一个用字符串表示的非负整数num和整数 $k$ ，移除这个数中的 $k$ 个数字，使得剩下的数字最小。以字符串形式返回这个最小的数字。

数据范围：
$1\le k \le num.length\le 10^5$

题解：

使用单调增栈维护最小的数。如果当前已经移除了 $k$ 个那么就不能进行出栈操作了。对得到的字符串去除前导零，如果删除字符个数小于 $k$ ，那么删掉末尾的 $k - cnt$ 个。如果剩余字符个数小于 $k - cnt$ ，返回 $0$ 。

如果删除前导零也计入删除个数，会变得比较麻烦，需要在出栈之后，如果入栈元素是 $0$ 就continue掉，把 $0$ 删掉，不入栈。

代码：

auto optimize_cpp_stdio = []()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    return 0;
}();
class Solution
{
public:
    string removeKdigits(string num, int k)
    {
        if (num.size() <= k)
            return "0";
        string st;
        int n = num.size();
        int cnt = 0;
        for (int i = 0; i < n; ++i)
        {
            while (st.size() && cnt < k && st.back() > num[i])
            {
                cnt++;
                st.pop_back();
            }
            st.push_back(num[i]);
        }

        int index = 0;
        while (index < st.size() && st[index] == '0')
        {
            index++;
        }
        st = st.substr(index);
        if (st.size() == 0 || st.size() < k - cnt)
            return "0";
        if (cnt == k)
        {
            return st;
        }
        else
        {
            return st.substr(0, st.size() - (k - cnt));
        }
    }
};