算法随笔_32: 移掉k位数字

上一篇:算法随笔_31:移动零-CSDN博客

=====

题目描述如下:

给你一个以字符串表示的非负整数 num 和一个整数 k ，移除这个数中的 k 位数字，使得剩下的数字最小。请你以字符串形式返回这个最小的数字。

示例 1 ：

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

=====

算法思路:

根据题目的要求，让我们首先来思考一下，如果仅移除一位数字，我们需要移除哪位数字，才能保证剩下的数字最小？

如果我们在任意一处删除一位数字i，后面的数字会依次前提。因此，要保证剩下的数字最小，我们需要让数字i后面的数字j小于数字i。这是第一点。

第二点，如果要保证整体的数字最小，我们需要从高位开始寻找需要删除的数字。找到了符合第一点的情况，那么我们就可以删除数字i了。如果需要删除两个及以上的数字，我们需要仍然需要用数字j和数字i之前的数字依次比较，如果仍符合第一点，我们仍需要删除前面的数字。

根据第二点的特征，我们发现在找到第一点之前保留的数字是递增的。在找到第一点之后我们需要从保留的数字从后往前依次删除数字。这是一个明显的单调栈的数据结构。我们可以基于此数据结构写出下面的算法:

1.  设数组num_new来表示这个单调栈。初始化后，把num[0]放入数组。再设del_k表示已经删除了几位数。初始化为0。

2.  我们从左往右枚举字符串num。

3. 对于访问到的元素i和num_new的末尾数字比较。如果小于num_new的末尾数字，我们需要弹出num_new的末尾数字，且del_k加1。循环此步骤。如果大于，则把nums[i]放入num_new数组。继续枚举字符串num。

4. 如果枚举完成后所有数字依次递增，那么我们需要从后往前逐个删除k位数字。最后我们要删除数组中的所有前置零。如果数组为空，返回字符串"0"。

代码实现中还有一些细节问题需要注意，请参考下面代码:

class Solution(object):
    def removeKdigits(self, num, k):
        """
        :type num: str
        :type k: int
        :rtype: str
        """
        num_len=len(num)
        num_new=[num[0]]
        del_k=0
        
        for i in range(1,num_len):

            while len(num_new)>0 and num[i]<num_new[len(num_new)-1] and del_k < k:
                num_new.pop()
                del_k+=1
            num_new.append(num[i])
        
        while del_k < k:
            num_new.pop()
            del_k+=1

        res="".join(num_new).lstrip('0')
        if res=="":
            res="0"
        return res