402. 移掉K位数字

 方法一：

class Solution {
    public String removeKdigits(String num, int k) {
        int n = num.length();
        if(n <= k) return "0";
        StringBuilder sb = new StringBuilder(num);
        for(int i = 0; i < k; i++) {
            int idx = 0;                 // 找到第一个大于后面的字符删除它
            for(int j = 1; j < sb.length() && sb.charAt(j) >= sb.charAt(j-1); j++) idx = j;
            sb.delete(idx,idx+1);               // 去除前导0
            while(sb.length() > 1 && sb.charAt(0) == '0') sb.deleteCharAt(0);
        }
        return sb.toString();
    }
}

方法二：单调栈

class Solution {
    public String removeKdigits(String num, int k) {
        int n = num.length();
        if(n <= k) return "0";
        Stack<Integer> stack = new Stack<>();
        for(int i = 0; i < n; i++) {
            int m = num.charAt(i) - '0';
            while(k > 0 && !stack.empty() && stack.peek() > m) {
                k--;            // 记录每一个之前大于当前元素的值，删除它
                stack.pop();
            }
            stack.push(m);
        }
        while(k-- > 0) {
            stack.pop();
        }
        StringBuilder sb = new StringBuilder();
        while(!stack.empty()) {
            sb.append(stack.pop());
        }
        while(sb.length() > 1 && sb.charAt(sb.length()-1) == '0') {
            sb.deleteCharAt(sb.length()-1);
        }
        return sb.reverse().toString();
    }
}