题目

给你一个以字符串表示的非负整数 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 。

思路

根据题意，说要移除k位后保留最小的数字，也就是说，当字符大小从左向右递减时，尽量保留位数较低的，移除位数较高的。反之要移除位数较低的。可以使用单调递增栈来实现这一目的，下面是具体实现

使用一个 Deque (双端队列)来存储处理过的数字字符，并构建单调递增栈。
遍历输入字符串 num 中的每个字符 c:
- 如果当前 k 大于 0 且栈不为空,并且当前字符 c 小于栈顶元素,则不断从栈顶弹出元素,直到 k 减为 0 或者栈为空。这样可以确保删除较大的数字,使剩余数字尽可能小。
- 如果当前字符 c 不是 '0' 或者栈不为空,则将 c 压入栈中。这样可以保留前导 0,确保最终结果不会以 0 开头。
如果处理完整个字符串后 k 仍然大于 0,说明需要继续从栈顶删除元素,直到 k 减为 0 或者栈为空。
最后,从栈底到栈顶依次取出元素,构造最终结果字符串。如果结果字符串为空,则返回 "0"。

总之整个遍历的关键点在于：

(1) 使用栈来维护当前构建的最小数字。

(2) 通过比较当前字符与栈顶元素的大小,决定是否删除栈顶元素。

(3) 处理前导 0 的情况,确保最终结果不会以 0 开头。

(4) 处理 k 大于输入字符串长度的情况。

代码实现

public static String removeKdigits(String num, int k) {
    Deque<Character> stack = new ArrayDeque<>(num.length());
    for(char c : num.toCharArray()){
        while(k > 0 && !stack.isEmpty() && c < stack.peek()){
            stack.pop();
            k--;
        }
        if( c != '0' || !stack.isEmpty()){
            stack.push(c);

        }
    }
    while( k > 0 && !stack.isEmpty()){
        stack.pop();
        k--;
    }

    StringBuffer buffer = new StringBuffer();
    while(!stack.isEmpty()){
        buffer.append(stack.pollLast());
    }

    return buffer.length() == 0 ? "0" : buffer.toString();
}

时间复杂度为O(n)，空间复杂度也为O(n)