题目来源

• leetcode：402. 移掉 K 位数字Remove K Digits

题目描述

题目解析

题意

要求从一个字符串数字中删除k个数字，使得剩下的数最小。也就是说，我们要保存原来的数字的相对位置不变

以题目中的 num = 1432219， k = 3 为例，我们需要返回一个长度为4的字符串。问题是：我们怎么才能求出这四个位置依次是什么呢？

思路

暴力法的话，我们需要枚举$C_n^{(n-k)}$ 种序列（其中 n 为数字长度），并逐个比较最大。这个时间复杂度是指数级别的，必须进行优化。

一个思路是：

• 从左到右遍历
• 对于每一个遍历到的元素，我们决定是丢弃还是保留

问题是：我们怎么知道，一个元素是应该丢弃还是保留呢？

前置知识：

• 对于两个数 123a456 和 123b456
  • 如果a > b，那么数字 123a456 > 123b456;
  • 如果a < b，那么数字 123a456 < 123b456;
• 也就是说，两个相同位数的数字大小关系取决于第一个不同的数的大小

因此我们的思路就是：

• 从左到右遍历
• 对于遍历到的元素，我们选择保留。 但是我们可以选择性丢弃前面相邻的元素。丢弃与否的依据如上面的前置知识中阐述中的方法。
• 也就是说，对于遍历到的元素（从第二个元素开始），与前面的元素进行比较
  • 如果比前一个元素小，就把前一个元素[替换成当前小的元素]
  • 如果大于等于前一个元素，则该元素直接拼接到最后面

以题目中的 num = 1432219， k = 3 为例的图解过程如下：

• 由于没有左侧相邻元素，因此没办法丢弃。
  

• 由于 4 比左侧相邻的 1 大。如果选择丢弃左侧的 1，那么会使得剩下的数字更大（开头的数从 1 变成了 4）。因此我们仍然选择不丢弃（因为字典序要求最小）
  

• 由于 3 比左侧相邻的 4 小。 如果选择丢弃左侧的 4，那么会使得剩下的数字更小（开头的数从 4 变成了 3）。因此我们选择丢弃。

• …

然而需要注意的是，如果给定的数字是一个单调递增的数字，那么我们的算法会永远选择不丢弃。这个题目中要求的，我们要永远确保丢弃 k 个矛盾。

一个简单的思路是：

• 每次丢弃一次，k减去1。当k减到0时，我们提前终止遍历
• 而当遍历完成，如果k仍然大于0。不妨假设最终还剩下x个需要丢弃，那么我们需要选择删除末尾 x 个元素。

上面的思路可行，但是稍显复杂。

我们需要把思路逆转过来。刚才我的关注点一直是丢弃，题目要求我们丢弃 k 个。反过来说，不就是让我们保留 n - kn−k 个元素么？其中 n 为数字长度。 那么我们只需要按照上面的方法遍历完成之后，再截取前n - k个元素即可。

按照上面的思路，我们来选择数据结构。由于我们需要保留和丢弃相邻的元素，因此使用栈这种在一端进行添加和删除的数据结构是再合适不过了