题目描述：

LeetCode 402. Remove K Digits

Given a non-negative integer num represented as a string, remove k digits from the number so that the new number is the smallest possible.

Note:

• The length of num is less than 10⁵ and will be ≥ k.
• The given num does not contain any leading zero.

Example 1:

Input: num = "1432219", k = 3
Output: "1219"
Explanation: Remove the three digits 4, 3, and 2 to form the new number 1219 which is the smallest.

Example 2:

Input: num = "10200", k = 1
Output: "200"
Explanation: Remove the leading 1 and the number is 200. Note that the output must not contain leading zeroes.

Example 3:

Input: num = "10", k = 2
Output: "0"
Explanation: Remove all the digits from the number and it is left with nothing which is 0.

题目大意：

给定一个用字符串表示的非负整数num，从中移除k位数字，使得剩下的数字尽可能小。

注意：

数字的长度小于10^5并且≥k。

给定的数字不包含前导0。

解题思路：

解法I 利用栈（Stack）数据结构

使得栈中的数字尽可能保持递增顺序。

Python代码：

class Solution(object):
    def removeKdigits(self, num, k):
        """
        :type num: str
        :type k: int
        :rtype: str
        """
        size = len(num)
        stack = ['0']
        for x in range(size):
            while stack[-1] > num[x] and len(stack) + k > x + 1:
                stack.pop()
            stack.append(num[x])
        while len(stack) > size - k + 1:
            stack.pop()
        return str(int(''.join(stack)))

解法II 问题可以转化为对偶问题：从字符串num中选取size - k个字符，使得选出的数字最小化。

首先利用字典numd保存数字'0' - '9'在原始字符串num中的出现位置。

然后循环size - k次：

按照'0' - '9'的顺序从numd中选取位置合法的数字

位置合法包含2条原则：1) 候选数字之后剩余的数字要足够多，2) 候选数字要处在已选出的数字之后

Python代码：

class Solution(object):
    def removeKdigits(self, num, k):
        """
        :type num: str
        :type k: int
        :rtype: str
        """
        size = len(num)
        ans = '0'
        numd = collections.defaultdict(collections.deque)
        for i, n in enumerate(num):
            numd[n].append(i)
        p = 0
        for x in range(size - k):
            for y in '0123456789':
                while numd[y] and numd[y][0] < p:
                    numd[y].popleft()
                if numd[y] and numd[y][0] <= k + x:
                    p = numd[y][0]
                    ans += y
                    numd[y].popleft()
                    break
        return str(int(ans))

 

本文链接：http://bookshadow.com/weblog/2016/09/18/leetcode-remove-k-digits/
请尊重作者的劳动成果，转载请注明出处！书影博客保留对文章的所有权利。

如果您喜欢这篇博文，欢迎您捐赠书影博客： ，查看支付宝二维码