力扣 402. 移掉K位数字 简单单调栈

题目链接

    /**
     * 简单单调栈
     * 题目思路是：用栈来读取字符串（从前往后读），如果当前堆顶数字比字符串中的数字大，则抛出（至于为什么能成立，贪心，细节都在代码中）
     *       来个例子
     *               stack    String
     *                 3，3        2       此时抛出 3 （抛出3之后，堆顶元素依然3大于2，接着抛出）
     *
     */
    public String removeKdigits(String num, int k) {
        // 如果字符串为空，或者 K 的值大于字符串的长度
        if (num.length() <= k || num == null) {
            return "0";
        }
        // 栈
        Stack<Character> stack = new Stack<>();
        for (int i = 0; i < num.length(); i++) {
            // 如果栈中没有元素则不需要进行比较
            // 如果栈顶元素大于字符串的数字，才会触发抛出
            while (k > 0 && !stack.isEmpty() && stack.peek() > num.charAt(i)) {
                k--;
                //System.out.println("抛出 ： " + stack.peek());
                stack.pop();
            }
            //去除前导零
            if (stack.isEmpty() && num.charAt(i) == '0') {
                continue;
            }
            stack.add(num.charAt(i));
        }

        StringBuilder sb = new StringBuilder();
        // 将堆中的数字放入字符串中
        while (!stack.isEmpty()) {
            // 如果还能减少数字，那么一定是从尾部开始减少（仔细想想为什么）
            if (k > 0) {
                stack.pop();
                k--;
                continue;
            }
            sb.append(stack.pop());
        }
        if (sb.length() == 0) return "0";
        return sb.reverse().toString();
    }