子序列

• 402. 移掉 K 位数字

402. 移掉 K 位数字

Leetcode

class Solution {
    public String removeKdigits(String num, int k) {
        // 使用栈删除 x (<=k) 个元素
        Deque<Character> deque = new LinkedList<Character>();
        int n = num.length();      
        for (int i = 0; i < n; ++i) {
            char digit = num.charAt(i);
            while (!deque.isEmpty() && k > 0 && deque.peekLast() > digit) {
                deque.pollLast();
                k--;
            }
            deque.offerLast(digit);
        }
        // 如果 k > 0，继续删除剩余
        for (int i = 0; i < k; ++i) {
            deque.pollLast();
        }
        // 删除前导 0，然后转成 String 返回
        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();
    }
}