移掉K位数字

发表于 分类于 阅读次数：

移掉K位数字（难度：中等）

1

方法：单调栈

维护一个递增栈，但当前元素小于栈顶元素，则移掉栈顶元素。

思路

转自

作者：monkeybing 链接：https://leetcode-cn.com/problems/remove-k-digits/solution/cyu-yan-zhan-shi-xian-tan-xin-suan-fa-by-monkeybin/ 来源：力扣（LeetCode）

本题采用贪心思路：

  1. 如果字符串按照数字大小升序排列，只需要删除最后K个字符即可；
  2. 如果非升序排列，需要从前到后遍历，删除字符串中每个逆序排列的字符。由于是从前到后遍历，所以先删除的一定是高位的数字，可以保证删除后得到的最终数字最小。

举例来说：如果字符串num = "123456789", k = 3，我们只需要删除最后3个数字，得到"123456". 如果字符串num = "1432219", k = 3，需要从前到后遍历查找逆序数字，进行删除，第一个逆序数字为'4'，第二个逆序数字为'3'，第三个逆序数字为第二个'2'，最后得到"1219"。

所以可以采用栈实现，每次遍历，判断如果栈非空，且当前数字大于栈顶数字，且k还有剩余（不为0），将栈顶数字出栈。最后将当前数字入栈。 如果遍历完成后，k仍有剩余，则依次将栈顶数字出栈。最后栈中保存的数字即为所求。按照从栈底到栈顶输出即可。 注意：特判场景，如果最后所有数字均出栈，即栈为空，需要返回"0"。

代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution:
    def removeKdigits(self, num: str, k: int) -> str:
        if not num or k <=0:
            return num
        
        stack = []
        for c in num:
            while stack and k > 0 and stack[-1] > c:
                stack.pop()
                k -= 1
            stack.append(c)
        
        while k > 0:
            stack.pop()
            k -= 1

        if not stack:
            return '0'
        
        return str(int(''.join(stack)))
2
复杂度

时间复杂度：O(n).

空间复杂度：O(n).