[刷题防痴呆] 0402 - 移掉k位数字 (Remove K

题目地址

https://leetcode.com/problems/remove-k-digits/

题目描述

402. Remove K Digits

Given string num representing a non-negative integer num, and an integer k, return the smallest possible integer after removing k digits from num.

 

Example 1:

Input: num = "1432219", k = 3
Output: "1219"
Explanation: Remove the three digits 4, 3, and 2 to form the new number 1219 which is the smallest.
Example 2:

Input: num = "10200", k = 1
Output: "200"
Explanation: Remove the leading 1 and the number is 200. Note that the output must not contain leading zeroes.
Example 3:

Input: num = "10", k = 2
Output: "0"
Explanation: Remove all the digits from the number and it is left with nothing which is 0.

思路

• 用栈来维护要留下来的数字字符.
• 如果当前字符小于栈顶的字符, 并且k仍大于0, 则移除栈顶的字符.
• 之后把当前字符扔到栈中等待判定.
• 栈中维护的字符是单调递增的.

关键点

• 注意, 最后看k的大小, 需要判断是否还需要删除, 如果需要删除, 从栈顶依次删除.
• 最后判断是否全为0, 并把左边多余的0删除掉.

代码

• 语言支持：Java

class Solution {
    public String removeKdigits(String num, int k) {
        char[] sc = num.toCharArray();
        Deque<Character> stack = new ArrayDeque<>();
        int n = sc.length;

        for (int i = 0; i < n; i++) {
            char c = sc[i];
            while (!stack.isEmpty() && stack.peek() > c && k > 0) {
                stack.pop();
                k--;
            }
            stack.push(c);
        }
        for (int i = 0; i < k; i++) {
            stack.pop();
        }
        StringBuilder sb = new StringBuilder();
        boolean isCheckZero = true;
        while (!stack.isEmpty()) {
            char c = stack.pollLast();
            if (isCheckZero && c == '0') {
                continue;
            }
            isCheckZero = false;
            sb.append(c);
        }
        if (sb.length() == 0) {
            return "0";
        }
        return sb.toString();
    }
}