1 题目描述

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

注意:

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

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

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

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

2 题解

很明显的一个贪心问题，关键点在于我们呢如何去选择这k个数。我们需要剩下的数字尽可能小，那么就得是高位得数字尽量小，也就是字符串前面得数字尽量小。那么策略来了。对于num, 只要num[i] > num[i+1]，num[i]就是我们要删除得那个。比如45879,当k=1时，删除8得到4579是最有得，这就是所贪的地方。

我们每次删除一个串然后在去寻找下一个，删除串得到新串，要么太耗时要么太要么太耗内存(取决于是原地操作，还是返回新对象)，这时我们可以考虑考虑利用栈，而维护一个单调栈恰恰和上面的贪心策略一样。

遍历num,对于当前元素val,如果小于栈顶元素，将栈顶元素出栈，k递减,然后将该元素入栈。
当k=0时，说明已经删除完了，将num中剩下的入栈，然后将栈倒序连接起来返回就是。
当num遍历完时，k>0,说明还得删除一些，那么现在栈式一个单调栈，只需进行k次出栈操作即可，最后将栈倒序连接起来返回。
关于去除前导0,前导0是怎么加入的？栈位空且当前元素位0的情况下入栈的，那么我们取个逆好了，栈不为空或当前元素不位0

3 代码

下面得代码参考了官方题解：

class Solution:
    def removeKdigits(self, num: str, k: int) -> str:

        if num is None or len(num) == k:
            return "0"
        if k == 0:
            return num

        """ 构建单调栈 """
        num_stack = []
        for val in num:
            while k and num_stack and num_stack[-1] > val:
                num_stack.pop()
                k -= 1

            """ 去除前导0 """
            if val != '0' or num_stack:
                num_stack.append(val)

        """ 如果去除的还不够， 去除单调栈的后面的 """
        res = num_stack[:-k] if k else num_stack

        """ or ”0“ 的原因，测试用例10，1 """
        return "".join(res) or "0"

    def main(self):
        num = "10"
        k = 1
        print(self.removeKdigits(num, k))


if __name__ == '__main__':
    solution = Solution()
    solution.main()