402. 移掉 K 位数字

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

示例 1 ：

输入：num = "1432219", k = 3
输出："1219"
解释：移除掉三个数字 4, 3, 和 2 形成一个新的最小的数字 1219 。

示例 2 ：

输入：num = "10200", k = 1
输出："200"
解释：移掉首位的 1 剩下的数字为 200. 注意输出不能有任何前导零。

示例 3 ：

输入：num = "10", k = 2
输出："0"
解释：从原数字移除所有的数字，剩余为空就是 0 。

提示：

• 1 <= k <= num.length <= 105
• num 仅由若干位数字（0 - 9）组成
• 除了 0 本身之外，num 不含任何前导零

递增栈，使用双端队列。

当队列不为空，且还可以删除字符（k > 0），且队尾字符大于当前字符时，删除队尾字符再入队当前字符，这样栈中的元素是递增的。 比如 14329 转化成 129。如果 k 还大于 0（还可以继续删除）的话，继续删除队尾元素， 比如 129 删除成 12。根据队列元素构建最终结果时，需要忽略前导零。

如果想让结果尽可能小，那么清除数字分两步：

1. 先删除 num 中的若干数字，使得 num 从左到右每一位都单调递增。 比如 14329 转化成 129，这需要使用到单调栈技巧。
2. num 中的每一位变成单调递增的之后，如果 k 还大于 0（还可以继续删除）的话，则删除尾部的数字，比如 129 删除成 12。

class Solution {
    public String removeKdigits(String num, int k) {
        // 使用双端队列来维护最终结果
        Deque<Character> deque = new LinkedList<Character>();
        int length = num.length();

        // 遍历数字字符串中的每个字符
        // 每个元素最多被弹出一次，最多也只会被插入一次，因此插入和弹出操作的总次数是线性的，即 O(n)。
        for (int i = 0; i < length; ++i) {
            char digit = num.charAt(i);
            // 当队列不为空，且还可以删除字符（k > 0），且队尾字符大于当前字符时
            // 说明队尾字符不应在最终结果中，删除队尾字符。重点。
            while (!deque.isEmpty() && k > 0 && deque.peekLast() > digit) {
                deque.pollLast(); // 这里需要队列不为空
                k--; // 删除字符，k 减 1，这里需要k>0
            }
            // 将当前字符加入队列
            deque.offerLast(digit);
        }
        
        // 如果还未删除够 k 个字符，则继续从队尾删除
        for (int i = 0; i < k; ++i) {
            deque.pollLast();
        }
        
        // 构建最终结果，忽略前导零。leadingZero是为了区分前导零和中间的零，例如0010中的两类0.
        StringBuilder ret = new StringBuilder();
        boolean leadingZero = true;
        while (!deque.isEmpty()) {
            char digit = deque.pollFirst();
            // 忽略前导零。例如0010，只把10加入ret。
            if (leadingZero && digit == '0') {
                continue;
            }
            leadingZero = false; // 一旦遇到非零字符，关闭前导零标志
            ret.append(digit);
        }
        
        // 如果最终结果为空，则返回 "0"
        return ret.length() == 0 ? "0" : ret.toString();
    }
}

• 时间复杂度：$O(n)$，其中 $n$ 为字符串的长度。尽管存在嵌套循环，但内部循环最多运行 $k$ 次。 由于 $0<k \leq n$，主循环的时间复杂度被限制在 $2n$ 以内。对于主循环之外的逻辑，它们的时间复杂度是 $O(n)$，因此总时间复杂度为 $O(n)$。
• 空间复杂度：$O(n)$。栈存储数字需要线性的空间。