题解 | #牛牛的数字游戏#

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param num string字符串
     * @param k int整型
     * @return string字符串
     */
    public String findSmallestNumber (String num, int k) {
        int n  = num.length();
        if (k >= n) {
            return "0";
        }
        Deque<Character> stack = new ArrayDeque<>();
        for (int i = 0; i < n; i++) {
            char c = num.charAt(i);
            // 栈不为空，栈顶元素大于当前字符并且k>0,因为找的是最小数字
            while (!stack.isEmpty() && stack.peekLast() > c && k > 0) {
                stack.pollLast();
                k--;
            }
            stack.offerLast(c);
        }
        // 如果k依然大于0，继续出栈
        while (k > 0) {
            stack.pollLast();
            k--;
        }
        StringBuilder stringBuilder = new StringBuilder();
        // 得到数字字符串，要正序得到
        while (!stack.isEmpty()) {
            stringBuilder.append(stack.removeFirst());
        }
        // 去除前导0
        while (stringBuilder.length() > 1 && stringBuilder.charAt(0) == '0') {
            stringBuilder.deleteCharAt(0);
        }
        return stringBuilder.toString();
    }
}

本题知识点分析：

1.贪心算法

2.栈的出栈和出栈

3.字符串StringBuilder单线程最快

本题解题思路分析：

1.如果k>=字符串长度，表明返回的肯定是0

2.利用ArrayDeque，可以实现双端队列的功能，LinkedList也可以，性能差一点

3.出栈条件： 栈不为空，栈顶元素大于当前字符并且k>0,因为找的是最小数字

4.如果k依然大于0，继续出栈

5.因为要得到数字，而栈是逆序存储，因此双端队列发挥作用，从首部拿到元素

6.去除前导0的情况

本题使用编程语言: Java

如果你觉得本篇文章对你有帮助的话，可以点个赞支持一下，感谢~