「每日LeetCode」2020年11月15日

本文最后更新于：2023年3月19日 晚上

Lt402. 移掉 K 位数字，单调栈

402. 移掉 K 位数字

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

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

示例 1 :

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

示例 2 :

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

示例** 3 :**

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

思路

在完成删除数量前，要保证当前栈是一个单调增的栈。
转自：https://leetcode-cn.com/problems/remove-k-digits/solution/wei-tu-jie-dan-diao-zhan-dai-ma-jing-jian-402-yi-d/

  • 从左遍历，还不知道当前的数要不要删，先入栈暂存，保留对它的记忆
  • 123531 这样「高位递增」的数，要删也删低位，不会考虑删高位的。
  • 432135 这样「高位递减」的数，肯定想干掉高位，尽量变成「高位递增」
  • 所以，如果当前数比栈顶更大，就还是递增态，是满意的，入栈。
  • 如果当前数比栈顶更小，要删栈顶的数，为什么？也许后面还有更大的呢？
    • 因为栈顶的数在高位，删掉它，后面小的数顶上，高位变小比起低位变小，减小幅度更大。
1
2
3
4
5
6
7
8
9
"1432219"  3
bottom[1        ]top  1入（没有左侧相邻元素，无法丢弃）
bottom[1 4      ]top  4入（4 比左侧相邻的 1 大。丢弃1，那么会使数字更大。不丢弃。）
bottom[1 3      ]top	4出	3入（3 比左侧相邻的 4 小。丢弃4，那么会使数字更小。丢弃。）
bottom[1 2      ]top	3出	2入（2 比左侧相邻的 3 小。丢弃3，那么会使数字更小。丢弃。）
bottom[1 2 2    ]top  2入  （2 于左侧相邻的 2 一样大。不丢弃。）
bottom[1 2 1    ]top	2出	1入 （1 比左侧相邻的 2 小。丢弃2，那么会使数字更小。丢弃。出栈满3个，停止出栈。）
bottom[1 2 1 9  ]top  9入
照这么做，如果是 "0432219"，如下，循环结束后，还得处理栈中的前导"0"。
1
2
3
4
5
6
7
8
"0432219"  3
bottom[0        ]top  0入
bottom[0 4      ]top  4入
bottom[0 3      ]top	4出	3入
bottom[0 2      ]top	3出	2入
bottom[0 2 2    ]top  2入
bottom[0 2 1    ]top	2出	1入  出栈满3个，停止出栈
bottom[0 2 1 9  ]top  9入

能不能限制不让前导 0 入栈？
加一个判断：栈为空且当前字符为 “0” 时，不入栈。取反，就是：

1
if (number !== "0" || stack.length > 0) stack.push(number);

遍历结束后，如果还没删够 k 个字符，开一个循环从栈中删栈顶。
如果栈变空了，返回 “0”，否则将栈中的字符转成字符串返回。

解答

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
/**
 * @param {string} num
 * @param {number} k
 * @return {string}
 */
var removeKdigits = function (num, k) {
  if (num.length <= k) return "0";
  const stack = [];
  for (const number of num) {
    while (k > 0 && stack.length > 0 && stack[stack.length - 1] > number) {
      stack.pop();
      k--;
    }
    if (number !== "0" || stack.length > 0) stack.push(number);
  }
  while (k > 0) {
    stack.pop();
    k--;
  }
  return stack.length ? stack.join("") : "0";
};