leetcode402（移掉K位数字：贪心算法）

给定一个以字符串表示的非负整数 num，移除这个数中的 k 位数字，使得剩下的数字最小。 输入: num = “1432219”, k = 3 输出: “1219” 解释: 移除掉三个数字 4, 3, 和 2 形成一个新的最小的数字 1219。

题解：贪心算法，对于任意一个数，一定是越靠前的数字越小，整个数字越小，为了让移除K位数字后的数尽量的小，我们可以采用贪心算法，遍历原字符串num，当num[ i ]<=num[ i+1 ]时，指针后移，当num[ i ]>num[ i+1 ]时，移除num[ i ]以及num[ i ]之前比num[ i+1 ]大的数，直到移除的数的总数量为k或num[ i ]之前所有数字都被移除，在继续后移指针，重复上述操作，直到K个数字都被移除完。如果遍历完num后，依然没有移除完k个数，则从末尾往前移除数字，直到移除的数字个数为K为止。为了优化算法，我们可以用到栈来存储当前已经遍历到的所有数字。

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();
    }
}