题目描述

给定一个以字符串表示的非负整数 num，移除这个数中的 k 位数字，使得剩下的数字最小.

样例

输入1432219
输出1219

算法1

(队列实现大的贪心算法) $O(n)$

时间复杂度

参考文献

java代码

lass Solution {
//双端队列来实现
    public String removeKdigits(String num, int k) {
        Deque<Character> q = new LinkedList<>();
        int i = 0;
        while(i<num.length()){
            while(!q.isEmpty()&&k>0&&q.peekLast()>num.charAt(i))
            {
                k--;
                q.pollLast();
            }
            q.offerLast(num.charAt(i));
            i++;
        }//保证全加进去了，并且是在加进去之前就是搞好的单调栈
        while(k-->0&&!q.isEmpty()) q.pollLast();
        while(!q.isEmpty()&&q.peekFirst()=='0') q.pollFirst();
        if(q.isEmpty()) return "0";
        String str = "";
        while(!q.isEmpty()) str +=q.pollFirst();
        return str;
    }
}

算法2

(双指针实现贪心算法) $O(n^2)$

时间复杂度

参考文献

java 代码

class Solution {
    public String removeKdigits(String num, int k) {
        //双指针
        int n = num.length();
        int r = 0;
        char res[] = new char[n];
        //遍历入队
        for(char c:num.toCharArray()){
            while(r>0&&k>0&&res[r-1]>c)
            {
                k--;
                r--;
            }
            res[r++]=c;
        }
        //System.out.println(Arrays.toString(res)+"-"+r);
        //就是本身就是递增序列的情况,从结尾开始删除
        while(k-->0&&r>0) r--;
        //移除头部的0
        int l = 0;
        while(l<r&&res[l]=='0') l++;
        if(r==l) return "0";
        return new String(res,l,r-l);、
//字符数组构建字符串时，后一个参数是长度
//字符串substring（），后一个参数是之前是子串结果的索引。
    }
}