来源

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/remove-k-digits

描述

给定一个以字符串表示的非负整数 num，移除这个数中的 k 位数字，使得剩下的数字最小。

注意:
num 的长度小于 10002 且 ≥ k。
num 不会包含任何前导零。

示例 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. class Solution {
  2.     public String removeKdigits(String num, int k) {
  3.         LinkedList<Character> stack = new LinkedList<Character>();
  5.         for (char digit : num.toCharArray()) {
  6.             while (stack.size() > 0 && k > 0 && stack.peekLast() > digit) {
  7.                 stack.removeLast();
  8.                 k -= 1;
  9.             }
  11.             stack.addLast(digit);
  12.         }
  14.         for (int i = 0; i < k; i++) {
  15.             stack.removeLast();
  16.         }
  18.         StringBuilder ret = new StringBuilder();
  19.         boolean leadingZero = true;
  20.         for (char digit : stack) {
  21.             if (leadingZero && digit == '0') {
  22.                 continue;
  23.             }
  25.             leadingZero = false;
  26.             ret.append(digit);
  27.         }
  30.         if (ret.length() == 0) {
  31.             return "0";
  32.         }
  33.         return ret.toString();
  34.     }
  35. }

复杂度分析

  • 时间复杂度：402. 移掉K位数字(Remove K Digits) - 图1。尽管存在嵌套循环，但内部循环最多只能运行402. 移掉K位数字(Remove K Digits) - 图2次。由于402. 移掉K位数字(Remove K Digits) - 图3，主循环的时间复杂度被限制在402. 移掉K位数字(Remove K Digits) - 图4以内。对于主循环之外的逻辑，它们的时间复杂度是402. 移掉K位数字(Remove K Digits) - 图5。总时间复杂度为402. 移掉K位数字(Remove K Digits) - 图6。
  • 空间复杂度：402. 移掉K位数字(Remove K Digits) - 图7，在最坏的情况下栈存储了所有的数字。