🌕🌕 402. 移掉 K 位数字

难度: 🌕🌕

问题描述

---

解法

class Solution {
    public String removeKdigits(String num, int k) {
        // 思路：
        // 单调栈
        int len = num.length();
        if(k >= len) {
            return "0";
        }
        int count = 0; // 已经移除的位数
        LinkedList<Integer> stack = new LinkedList<>();
        int index = 0;
        for(; index < len; index ++) {
            char c = num.charAt(index);
            int val = c - '0'; // 获取当前位的值
            if(stack.isEmpty() || val >= stack.peek()) {
                stack.push(val); // 比栈顶元素大，压栈
            } else {
                // 比栈顶元素小，需要弹栈，弹出的元素就是需要移除的元素
                while(!stack.isEmpty() && val < stack.peek()) {
                    stack.pop();
                    count ++;
                    // 判断是否满足需要移除的元素个数
                    if(count >= k) {
                        break;
                    } 
                }
                if(count >= k) {
                    break;
                } 
                stack.push(val);
            }
        }
        // 取出栈中元素
        StringBuilder sb = new StringBuilder();
        if(count < k) {
            // 删除的元素不够，从后往前删除栈顶元素
            while(count < k) {
                stack.pop();
                count ++;
            }
        }
        while(!stack.isEmpty()) {
            sb.insert(0, stack.pop());
        }
        // 将后续元素添加到 sb 后面
        if(index < len) {
            sb.append(num.substring(index, len));
        }
        // 去掉 sb 的前导 0
        String str = sb.toString();
        int tmp = 0;
        for(int i = 0; i < str.length(); i ++) {
            if(str.charAt(tmp) == '0') {
                tmp ++;
            } else {
                break;
            }
        }
        // System.out.println(str + "  " + tmp);
        if(tmp == str.length()) {
            return "0";
        }
        // 最多保留 len - k 个元素
        return str.substring(tmp, Math.min(tmp + len - k, str.length()));
    }
}

---

输出