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

解释: 从原数字移除所有的数字,剩余为空就是 0。

问题的关键是:我们怎么知道,一个元素是应该保留还是丢弃呢?

也就说,两个相同位数的数字大小关系取决于第一个不同的数的大小。

丢弃与否的依据如上面的前置知识中阐述中的方法。

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

一个简单的思路就是:

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

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