题目

思路

1. It feels useless to sort the numbers,Backtracking should be used for circular comparisons.
2. wrote a backtrace,超出时间限制了…Backtracking is indeed time-complex,记录一下,润去题解

    //targetHow many numbers to remove for the target nowHow many digits to delete for the current charfor the last deleted character For backtracking
    public void Back(StringBuilder nownum,int target,int now){
    
        if(target==now){
    
            //比较两个字符串的大小 不能直接转 length will exceed
            //赋给ans
            ans = Compare(nownum.toString(),ans);
            return;
        }//Otherwise start subtracting
        for(int i=0;i<nownum.length();i++) {
    
            StringBuilder sb = new StringBuilder(nownum);
            Back(sb.deleteCharAt(i), target, now + 1);
        }
    }

3. Traverse the string from left to right,for each element traversed,See if you need to selectively discard the previous adjacent elements,因为对于aabbce来说,就可以判断aabbc好,还是aabbe好
4. 需要注意的是,If you encounter a monotonically increasing number,Then you will always choose not to discard,But the meaning of the question must be discardedk个,为了解决这个问题,You need to let it go every time you throw it awayk减去1,That is, a discard is completed,减到0traversal can be terminated,Because enough has been lostk次了.
5. 但也有可能,遍历结束后k还没有减到0,It can be reserved at this timen-kthe meaning of the numbers,So after traversal select beforen-k个即可.

代码

    public String removeKdigits(String num, int k) {
    
        int remain = num.length()-k;
        //创建stack用来接收
        Stack<Character> cs = new Stack<>();
        for(int i=0;i<num.length();i++){
    
            //弹出栈顶 It compares which is put on the stack
            while(k!=0 && !cs.isEmpty() && cs.peek()>num.charAt(i)){
    
                cs.pop();
                k-=1;
            }
            cs.push(num.charAt(i));
        }
        //取前n-k个
        StringBuilder ans = new StringBuilder();
        while(!cs.isEmpty()) ans.append(cs.pop());
        String ans1 = ans.reverse().substring(0,remain);
        //删除前导0
        int nums=0;
        for(int i=0;i<ans1.length();i++){
    
            if(ans1.charAt(i)=='0') nums++;
            else break;
        }
        if(nums==ans1.length()) return "0";
        else return ans1.substring(nums);
    }