题目主要信息

给定一个以字符串表示的数字 num 和一个数字 k ，从 num 中移除 k 位数字，使得剩下的数字最小。如果可以删除全部数字则剩下 0 1.num仅有数字组成 2.num是合法的数字，不含前导0 3.请你保证删除之后的num也不含前导0

方法一：单调栈

具体方法

遍历字符串，走到字符串的第i位置时，以i字符为中心，寻找左边最近比该字符小的字符。

​ 从左到右遍历字符串，如果栈非空&&栈顶元素>=当前字符&&k!=0，则弹栈，并最后将当前字符入栈。维护一个递增栈

• ​ 当k==0时，则说明弹栈次数用完了。
• ​ 当弹出0的时候，不需k--,因为前导0忽略。

​ 最后，当弹栈次数用完后，只需将栈中字符和未入栈字符拼接，即可得到数值最小化。

代码实现

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param num string字符串 
     * @param k int整型 
     * @return string字符串
     */
    public String removeKnums (String num, int k) {
        // write code here
        int len = num.length();
        //判断他特殊情况
        if(len == k){
            return "0";
        }
        char[] arr = num.toCharArray();
        char[] res = new char[len];
        int top=-1;
        int n = len-k;
        //遍历字符串
        for(char c : arr){
            //判断当前字符和栈顶元素大小
            while(k > 0 && top != -1 && res[top] > c){
                top--;
                k--;
            }
            //存入栈中
            res[++top] = c;
        }
        StringBuilder ans = new StringBuilder();
        //重构答案
        for(int i=0; i<n; i++){
            if(ans.length() ==0 && res[i] == '0'){
                continue;
            }
            ans.append(res[i]);
        }
        
        return ans.length() ==0 ? "0" : ans.toString();

    }
}

复杂度分析

• 时间复杂度：$O(n)O(n)$,遍历字符串。
• 空间复杂度：$O(n)O(n)$，存储栈空间。

方法二：贪心

具体方法

给定一个长度为$nn$的数字序列$x0,x1,x\mathrm{2...}xnx0,x1,x2...xn$,从左往右找到第一个位置i，使得,并删除$xi-1xi-1$;如果不存在，说明整个数字序列单调不降，删去最后一个数字即可。

基于此，可以每次对整个数字序列执行一次这个策略；删去一个字符后，剩下的 n-1长度的数字序列就形成了新的子问题，可以继续使用同样的策略，直至删除 k 次。

从左往右增量的构造最后的答案。可以用一个栈维护当前的答案序列，栈中的元素代表截止到当前位置，删除不超过 k 次个数字后，所能得到的最小整数。根据之前的讨论：在使用 k 个删除次数之前，栈中的序列从栈底到栈顶单调不降。

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

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

上述步骤结束后需要针对一些情况做额外的处理：

• 如果删除了$mm$ 个数字且 ，这种情况下我们需要从序列尾部删除额外的$k-mk-m$个数字。

• 如果最终的数字序列存在前导零，我们要删去前导零。

• 如果最终数字序列为空，我们应该返回 0。

  最终，从栈底到栈顶的答案序列即为最小数。

代码实现

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param num string字符串 
     * @param k int整型 
     * @return string字符串
     */
    public String removeKnums (String num, int k) {
        // write code here
       Deque<Character> deque = new LinkedList<>();
        int len = num.length();
        //单调栈判断 
        for (int i = 0; i < len; ++i) {
            char digit = num.charAt(i);
            // 判断当前是否大于栈顶
            while (!deque.isEmpty() && k > 0 && deque.peekLast() > digit) {
                deque.pollLast();
                k--;
            }
            //加入最后一个位置
            deque.offerLast(digit);
        }
        
        for (int i = 0; i < k; ++i) {
            deque.pollLast();
        }
        //返回最终结果
        StringBuilder res = new StringBuilder();
        boolean leadingZero = true;
        while (!deque.isEmpty()) {
            char digit = deque.pollFirst();
            //是否遇到0
            if (leadingZero && digit == '0') {
                continue;
            }
            leadingZero = false;
            res.append(digit);
        }
        return res.length() == 0 ? "0" : res.toString();
    }
}

复杂度分析

• 时间复杂度：$O(n)O(n)$，$nn$ 为字符串的长度。
• 空间复杂度：$O(n)O(n)$。栈存储数字需要线性的空间。