跳转至

LeetCode: 402. 移掉K位数字

1、题目描述

给定一个以字符串表示的非负整数 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。

2、解题思路

​ 这道题可以直接使用贪心法

​ 问题的关键在于为吃一个递增序列,这样得到的数字才是最小的

​ 首先来看这样的情况,一位一位来看,如果移除一位,使得当前数字变得最小,需要怎么做呢?

  • 从前向后扫描,如果当前数字比栈顶元素小,弹栈,k-1,如果大于栈顶元素,放入栈中

​ 最后,去除栈中前面的0,然后取出从第一个不为0的位置开始取,取出len(num-k-cnt),cnt表示0的个数

​ 也就是说,将后面最大的哪些元素去掉,剩下的就是最小的序列,

class Solution:
    def removeKdigits(self, num, k):
        """
        :type num: str
        :type k: int
        :rtype: str
        """
        buff = []

        n = k
        for i in num:
            while buff and n > 0 and i < buff[-1]:
                n -= 1
                buff.pop()
            buff.append(i)

        cnt = 0
        while cnt < len(buff) and buff[cnt] == '0':
            cnt += 1

        if cnt+n >= len(buff):
            return '0'

        return "".join(buff[cnt:len(buff)-n])