题目

题目来源：力扣（LeetCode）

给你一个以字符串表示的非负整数 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 。

思路分析

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

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

我们用一个单调递增栈维护当前的答案序列，栈中的元素代表截止到当前位置，删除不超过 k 次个数字后，所能得到的最小整数。

具体地：

  1. 遍历字符串 s，若当前栈不为空并且栈顶元素的值大于当前遍历的元素值并且移除元素的个数没有达到要求 k，则栈顶元素出栈，count 值加 1。

  2. 若当前遍历的元素比栈顶元素的值要大，则直接将该元素压栈。

  3. 若遍历完整个字符串而 count < k（移除的元素个数没有达到要求，示例：num = “123456”, k = 3），此时直接将栈中的前三个元素依次出栈，即 “ 654 “ 出栈剩下的 “ 321 “ 翻转一下，即为最小值。

  4. 若当前栈为空（去掉一个最大的元素后，其余元素均为 “ 0 “），则直接返回 “ 0 “ 即可。 ```javascript 示例：num = “100”, k = 1，初始：count = 0 i = 0，1 入栈 -> stack：(1)； i = 1，0 < 1 且 count < 1 -> stack：()，count = 1； i = 2，0 = 0，当前元素值为 0，并且栈为空，则直接跳过此次遍历；

因为栈为空，所以最终返回 “0”。

  2. **代码**
  3. ```javascript
  4. /**
  5.  * @param {string} num
  6.  * @param {number} k
  7.  * @return {string}
  8.  */
  9. var removeKdigits = function (num, k) {
  10.   let n = num.length;
  11.   if (n <= k || n === 1) return '0';
  13.   // 对前导0进行处理例如：“00200”
  14.   const handleStr = (str) => { 
  15.     let i = 0;
  16.     while (str[i] == 0) i++;
  17.     if (i == str.length) return '0'
  18.     return str.slice(i)
  19.   }
  21.   // 单调递增栈，维护当前的答案序列，栈中的元素代表截止到当前位置，删除不超过 kk 次个数字后，所能得到的最小整数
  22.   let stack = [];
  23.   // 记录栈顶元素删除的次数
  24.   let count = 0;
  25.   for (let i = 0; i < n; i++) {
  26.     // 当前值大于栈顶值，栈顶值出栈
  27.     while (stack.length && stack[stack.length - 1] > num[i]) { 
  28.       stack.pop();
  29.       // 栈顶值出栈次数加 1
  30.       count++;
  31.       // 栈顶值出栈最多只能出栈 k 次， 当 count === k 时，栈中元素不能再出栈
  32.       if (count === k) { // 当count === k" 直接返回
  33.         // 利用数组的 join() 方法，直接将栈中的元素转换成字符粗
  34.         return handleStr(stack.join('') + num.slice(i)) // 将栈里的元素和剩余未入栈的元素拼接后进行处理
  35.       }
  36.     }
  37.     stack.push(num[i])
  38.   }
  39.   // num 为正序例如'12345678'情况，count < k从尾部直接截取
  40.   if (count < k) return handleStr(stack.join('').slice(0, count - k));
  41. };