描述

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

示例

示例1：

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

示例2：

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

示例 3 ：

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

提示

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

解题思路

对于两个相同长度的数字序列，最左边不同的数字决定了这两个数字的大小，例如，对于 A=1axxx，B = 1bxxx，如果 a>b 则 A>B。

基于此，我们可以知道，若要使得剩下的数字最小，需要保证靠前的数字尽可能小。

我们可以用一个栈维护当前的答案序列，栈中的元素代表截止到当前位置，删除不超过 k 次个数字后，所能得到的最小整数。根据之前的讨论：在使用 k 个删除次数之前，栈中的序列从栈底到栈顶单调不降。

因此，对于每个数字，如果该数字小于栈顶元素，我们就不断地弹出栈顶元素，直到：

  • 栈为空
  • 或者新的栈顶元素不大于当前数字
  • 或者我们已经删除了 k 位数字

上述步骤结束后我们还需要针对一些情况做额外的处理：

  • 如果我们删除了 m 个数字且 m<k，这种情况下我们需要从序列尾部删除额外的 k−m 个数字。
  • 如果最终的数字序列存在前导零，我们要删去前导零。
  • 如果最终数字序列为空，我们应该返回 0。

代码

  1. class Solution {
  2.     public String removeKdigits(String num, int k) {
  3.         int n = num.length();
  4.         if (n == k) return "0";
  5.         int count = 0;
  6.         Deque<Character> deque = new LinkedList<Character>();
  7.         for (int i = 0; i < n; i++) {
  8.             while (!deque.isEmpty() && num.charAt(i) < deque.peekLast() && count < k) {
  9.                 deque.pollLast();
  10.                 count++;
  11.             }
  12.             deque.addLast(num.charAt(i));
  13.         }
  14.         while (count < k) {  //去掉末尾 k - count 个元素
  15.             deque.pollLast();
  16.             count++;
  17.         }
  18.         while (deque.peekFirst() == '0') {  // 去掉前置0
  19.             deque.pollFirst();
  20.             if (deque.isEmpty()) {
  21.                 return "0";
  22.             }
  23.         }
  24.         StringBuffer buf = new StringBuffer();
  25.         while (!deque.isEmpty()) {
  26.             buf.append(deque.pollFirst().toString());
  27.         }
  28.         String res = buf.toString();
  29.         return res;
  30.     }
  31. }

复杂度分析

时间复杂度：O(n)，其中 n 为字符串的长度。尽管存在嵌套循环，但内部循环最多运行 k 次。由于 0<k≤n，主循环的时间复杂度被限制在 2n 以内。对于主循环之外的逻辑，它们的时间复杂度是 O(n)，因此总时间复杂度为 O(n)。

空间复杂度：O(n)。栈存储数字需要线性的空间。