LeetCode_贪心算法_双端队列_中等_402.移掉 K 位数字

1.题目

给你一个以字符串表示的非负整数 num 和一个整数 k ，移除这个数中的 k 位数字，使得剩下的数字最小。请你以字符串形式返回这个最小的数字。

示例 1： 输入：num = “1432219”, k = 3 输出：“1219” 解释：移除掉三个数字 4, 3, 和 2 形成一个新的最小的数字 1219 。

示例 2： 输入：num = “10200”, k = 1 输出：“200” 解释：移掉首位的 1 剩下的数字为 200. 注意输出不能有任何前导零。

示例 3： 输入：num = “10”, k = 2 输出：“0” 解释：从原数字移除所有的数字，剩余为空就是 0 。

提示： 1 0)，使得 Di-1 > Di，然后删除 Di-1；如果不存在，说明整个数字序列单调不降，删除最后一个数字即可。 2）基于此，我们可以每次对整个数字序列执行一次这个策略；删去一个字符后，剩下的 n − 1 长度的数字序列就形成了新的子问题，可以继续使用同样的策略，直至删除 k 次。

③ 考虑从左往右增量的构造最后的答案。我们可以用一个双端队列维护当前的答案序列，队列中的元素代表截止到当前位置，删除不超过 k 次个数字后，所能得到的最小整数。根据之前的讨论：在使用 k 个删除次数之前，队首到队尾的元素是单调递增的。

3.代码实现（Java）

//思路1————贪心 & 双端队列
class Solution {
    public String removeKdigits(String num, int k) {
        int length = num.length();
        if (length == k) {
            return "0";
        }
        //定义一个双端队列
        Deque deque = new LinkedList();
        for (int i = 0; i  0 && deque.peekLast() > c) {
                //移除当前队尾元素
                deque.pollLast();
                //移除次数减一
                k--;
            }
            //将当前字符加入到队尾
            deque.offerLast(c);
        }
        //如果此时 k > 0，则说明队列 deque 中的元素已经是单调递增了，只需将队尾元素移除 k 次
        for (int i = 0; i