Python O(n) Solution Using Stack


  • 0

    Idea is similar to 321. Create Maximum Number.

    class Solution(object):
        def removeKdigits(self, num, k):
            """
            :type num: str
            :type k: int
            :rtype: str
            """
            from collections import deque
    
            sta = deque()
            sta.append(num[0])
            index, n = 1, len(num)
            if n == k:
                return '0'
            cnt = k
            while cnt > 0 and index < n:
                x = num[index]
                if x >= sta[-1]:
                    if len(sta) < n - k:
                        sta.append(x)
                else:
                    while sta and sta[-1] > x and len(sta) + n - index - 1 >= n - k:
                        sta.pop()
                        cnt -= 1
                    sta.append(x)
                index += 1
    
            while index < n:
                sta.append(num[index])
                index += 1
            res = ''.join(list(sta))
            if not res.lstrip('0'):
                return '0'
            else:
                return res.lstrip('0')
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.