[402][中等][贪心][栈] 移掉K位数字

题目描述

402. 移掉K位数字

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

注意:

• num 的长度小于 10002 且 ≥ k。

• num 不会包含任何前导零。

示例 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。

解题思路

对原始代表数字的字符串去掉固定的位数$k$, 保留下来的也是固定的位数$n-k$, 题目就变为了在原始字符串中, 选取一个固定长度的子序列, 而这个子序列的排序最小.

对于固定位数的数字大小, 同位的大小确定后, 后面位数的相对大小就不再重要, 因此需要尽量把小数字放在右边.

移掉K位数字

使用贪心算法的思路. 贪心算法即在每一步做出当前的最佳选择, 这个最佳选择不需要考虑全局.

对字符串从左到右循环, 我们的思路是在每一步判断对应的数字要不要丢弃. 如果当前位置的数字比它左边的数字(如果有的话)还要小, 说明丢弃前面的数字, 保留当前的数字, 会使得最终的结果变小.

整体思路如上, 还有些细节:

1. 如果字符串中的数字是递增的, 那么整个遍历就不会丢弃任何数字. 类似地也可能丢弃小于$k$个数字. 对于这种情况, 直接取前$n-k$个数字就好

这种与前一个数字比较的操作, 非常适合用栈结构来配合实现.

代码如下:

class Solution:
    def removeKdigits(self, num: str, k: int) -> str:
        stack = ['0']  # 增加一个哨兵, 没有一个数字比0小
        ramain_num = len(num) - k

        for n in num:
            while k and stack[-1] > n:
                stack.pop()
                k -= 1
            stack.append(n)
        res = ''.join(stack[1: ramain_num + 1]).lstrip('0')
        return res or '0'