【单调栈】移掉 K 位数字

题目

402. 移掉 K 位数字

---

给你一个以字符串表示的非负整数 num 和一个整数 k ，移除这个数中的 k 位数字，使得剩下的数字最小。请你以字符串形式返回这个最小的数字。

示例 1 ：

输入：num = "1432219", k = 3
输出："1219"
解释：移除掉三个数字 4, 3, 和 2 形成一个新的最小的数字 1219 。

示例 2 ：

输入：num = "10200", k = 1
输出："200"
解释：移掉首位的 1 剩下的数字为 200. 注意输出不能有任何前导零。

示例 3 ：

输入：num = "10", k = 2
输出："0"
解释：从原数字移除所有的数字，剩余为空就是 0 。

提示：

• 1 <= k <= num.length <= 105
• num 仅由若干位数字（0 - 9）组成
• 除了 0 本身之外，num 不含任何前导零

解题

方法一：单调栈

思路

将问题“删除 k 位数字”转化为“保留 len - k 位数字”。

普遍的，对于两个数 $abc\underline{x}\square\square\square$ 和 $abc\underline{y}\square\square\square$：

• 如果 $x>y$，则 $abcx\square\square\square > abcy\square\square\square$
• 否则，$abcx\square\square\square \leq abcy\square\square\square$

得出结论：两个相同位数的数字大小关系取决于第一个不同的数的大小

维护一个单调栈(stack)，栈中的元素代表截止到当前位置，删除不超过 k 次个数字后，所能得到的最小整数。 遍历字符串数字：

• 如果 k > 0 且栈不为空且当前遍历到的数字 n 小于栈顶元素，不断地弹出栈顶元素，k自减。
• 否则把栈顶元素入栈。

遍历完成后如果 k > 0 ，则需要把栈顶的 k 个元素出栈（删去多余数字）。 把栈中的字符全部出栈，并反向加入结果数字字符串。 如果结果数字字符串中存在前导零，则删除前导零。 此时如果结果数字字符串为空，则应该返回 "0" 否则返回结果数字字符串。

代码

class Solution {
    public String removeKdigits(String num, int k) {
        if (num.length() == k) return "0";
        Deque<Character> stack = new LinkedList<>();
        for (char n : num.toCharArray()) {
            while (k > 0 && !stack.isEmpty() && n < stack.peek()) {
                stack.pop();
                k--;
            }
            stack.push(n);
        }
        while (k-- > 0) stack.pop();
        StringBuilder ans = new StringBuilder();
        while (!stack.isEmpty()) {
            ans.insert(0, stack.pop());
        }
        while (ans.indexOf("0") == 0) {
            ans.deleteCharAt(0);
        }
        return ans.length() == 0 ? "0" : ans.toString();
    }
}

优化

在把栈转为结果数字的过程中去除前导零，避免字符串操作。

class Solution {
    public String removeKdigits(String num, int k) {
        if (num.length() == k) return "0";
        Deque<Character> deque = new LinkedList<>();
        for (char n : num.toCharArray()) {
            while (k > 0 && !deque.isEmpty() && n < deque.peek()) {
                deque.pop();
                k--;
            }
            deque.push(n);
        }
        while (k-- > 0) deque.pop();
        StringBuilder ans = new StringBuilder();
        boolean hasLeadingZero = true;
        while (!deque.isEmpty()) {
            char curr = deque.pollLast();
            if (hasLeadingZero && curr == '0') continue;
            hasLeadingZero = false;
            ans.append(curr);
        }
        return ans.length() == 0 ? "0" : ans.toString();
    }
}

优化

删去多余数字的操作也可以在把栈转为结果数字的过程中完成（从栈底部拉出 size - k 个元素，栈顶部就会留下多余的 k 个元素）。

class Solution {
    public String removeKdigits(String num, int k) {
        if (num.length() == k) return "0";
        Deque<Character> deque = new LinkedList<>();
        for (char n : num.toCharArray()) {
            while (k > 0 && !deque.isEmpty() && n < deque.peek()) {
                deque.pop();
                k--;
            }
            deque.push(n);
        }
        StringBuilder ans = new StringBuilder();
        boolean hasLeadingZero = true;
        while (deque.size() > k) {
            char curr = deque.pollLast();
            if (hasLeadingZero && curr == '0') continue;
            hasLeadingZero = false;
            ans.append(curr);
        }
        return ans.length() == 0 ? "0" : ans.toString();
    }
}