题目地址:https://leetcode.com/problems/remove-k-digits/description/

题目描述:

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 10002 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.

题目大意

从一个数字字符串中删除k个数字,使得剩下来的数字字符串是最小的。

解题方法

看了Topics知道这个是用栈来解决的题目。看了别人的解答才明白怎么回事。

使用一个栈作为辅助,遍历数字字符串,当当前的字符比栈最后的字符小的时候,说明要把栈的最后的这个字符删除掉。为什么呢?你想,把栈最后的字符删除掉,然后用现在的字符进行替换,是不是数字比以前的那种情况更小了?所以同样的道理,做一个while循环!这个很重要,可是我没有想到。在每一个数字处理的时候,都要做一个循环,使得栈里面最后的数字比当前数字大的都弹出去。

最后,如果K还没用完,那要删除哪里的字符呢?毋庸置疑肯定是最后的字符,因为前面的字符都是小字符。

很有意思的一个题目!

代码如下:

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

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21

DDKK.COM 弟弟快看-教程,程序员编程资料站,版权归原作者所有

本文经作者:负雪明烛 授权发布,任何组织或个人未经作者授权不得转发