leetcode回顾——[402] Remove K Digits

LeetCode

题目

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
给定一个以字符串表示的非负整数 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位数字，使得剩下的数字是最小，那么就希望这个数字最好是升序的；为了实现这个结果，利用一个栈，然后遍历数字的每一位数，如果发现这个数字比它左边的数字来的小，那么就把这个数字左边的数字舍弃，依次类推下去。

示例：num=1432219，k=2

1 4 3 2 2 1 9

开始遍历：

1入栈 –> 4入栈 –> 3入栈，3比4小，4出栈，3入栈 –> 2入栈，2比3小，3出栈，此时移除的数字以符合k，直接将剩余数字入栈

[1] –> [1,4] –> [1,4]=>[1,3] –> [1,3]=>[1,2]

最终答案：12219

AC代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution:
    def removeKdigits(self, num, k):
        """
        :type num: str
        :type k: int
        :rtype: str
        """
        if k == len(num):
            return '0'
        new_nums =[]
        for i in range(len(num)):
            while new_nums and num[i] < new_nums[-1] and k > 0:
                new_nums.pop()
                k -= 1
            new_nums.append(str(num[i]))
        if k > 0:
            new_nums = new_nums[:-k]
        while new_nums and new_nums[0] == '0':
            new_nums.pop(0)
        if not new_nums:
            return '0'
        return ''.join(new_nums)