LeetCode第402题移掉K位数字

1. 算法 单调栈、贪心
2. 核心思想 第一个数字a直接入栈，其他数字b与已经入栈的数字进行比较，如果b < a，则a出栈，直到①栈为空；②b >= a；③已经删除了k个数字. 此外还存在三个特殊情况：①删除的数字少于k，则从末尾删除；②存在零，删掉；③序列为空，返回0. 我采用的思路是贪心加递归，从前k个数中选择一个最小的(从这里开始错误，因为不保证在剩下的地方能找到其他小的），然后依次找其他数字。此这种方法还存在一个问题就是递归无法解决0的问题。
3. 代码

class Solution {
          
   
    public String removeKdigits(String num, int k) {
          
   
        Deque<Character> deque = new LinkedList<Character>();
        int length = num.length();
        for (int i = 0; i < length; ++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 ret = new StringBuilder();
        boolean leadingZero = true;
        while (!deque.isEmpty()) {
          
   
            char digit = deque.pollFirst();
            if (leadingZero && digit == 0) {
          
   
                continue;
            }
            leadingZero = false;
            ret.append(digit);
        }
        return ret.length() == 0 ? "0" : ret.toString();
    }
}