题解 | #移掉 K 位数字#

题目分析

题目给出了我们一个数字字符串，和一个数字k

题目说我们可以从字符串中去掉k位数字，返回最小数字字符串的方案

方法一：单调栈

实现思路
- 我们需要维护一个单调栈，将数字字符串每一个元素进行入栈处理（在这里我们用列表表示单调栈）
- 当取到的数字字符大于栈顶的时候，我们让数字正常入栈
- 当取到的数字字符小于栈顶的时候，我们就将栈顶元素出栈，并且一直比较新的栈顶元素，直到栈顶元素与取得元素相等或更小为止
- 出栈则说明我们去掉这个数字字符，相应k的值就需要自减

alt

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param num string字符串 
# @param k int整型 
# @return string字符串
#
class Solution:
    def removeKnums(self , num: str, k: int) -> str:
        # write code here
        stack = []
        for c in num:
            while stack and k and int(c) < int(stack[-1]):        # 维护单调栈的单调性
                k -= 1
                stack.pop()
            if not stack and c == '0':                                 # 如果现在stack开头的全是0就直接跳过
                continue
            stack.append(c)
        stack = stack[:-k] if k else stack
        if not stack:                                                  # 如果最后一个数也不剩下就说明应该结果是0
            stack.append('0')
        return ''.join(stack)                                        # 返回字符串形式

复杂度分析

时间复杂度： $O (n)$ ，一趟遍历的时间代价
空间复杂度： $O (n)$ ，开辟的栈空间的开销

方法二：贪心

实现思路
- 如果要剩下的数字最小，那么数字从左开始的每一位都要尽可能地小，因此我们要从剩余数字的高位开始，在有效范围内找到最小的数字。
有效范围：对于 num = "1432219", k = 3，要求删除 3 位数字，留下 4 位数字。那么第 1 位数字的查找有效范围是 1432，即下标 0 ~ 3。因为如果我们再往后选择，比如选择第 5 位数字 2，那么我们就无法完整地凑齐 4 位数字了。假设我们要从长度为 length 的字符串 num 中删除 k 位数字，那么第 x 个数字的有效查找范围是下标 x-1 ~ k+x-1
整体思路是：
- 从高位开始逐一查找每一位数字尽可能小的取值。其中，第 x 位数字的有效取值范围是 x-1 ~ k+x-1
- 找到最小值后记录最小值 min_num 以及对应的下标 min_index
- 设置下一轮的查找开始位置为 min_index + 1
- 循环此过程，直到完成所有数字的查找

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param num string字符串 
# @param k int整型 
# @return string字符串
#
class Solution:
    def removeKnums(self , num: str, k: int) -> str:
        # write code here
        num_length = len(num)
        if num_length <= k:
            return "0"
        
        left_count = num_length - k
        res = ""
        count = 0
        begin = 0
        
        while count < left_count:
            min_index = 0
            min_num = float('inf')
            for i in range(begin, k + count + 1):
                # 找到最小数
                if int(num[i]) < min_num:
                    min_index = i
                    min_num = int(num[i])
            # 把找到的最小数加入结果列表
            res += str(min_num)
            # 设置下一轮查找范围的起点
            begin = min_index + 1
            count += 1
            
        return "0" if len(res) == 0 else str(int(res))

复杂度分析

时间复杂度： $O (k n)$ ，最差的时间代价与k值有关，因此用 $O (k n)$ 表示
空间复杂度： $O (1)$ ，只引入常量级别的空间开销