Greedy Python Solution using Deque


  • 0
    B
    def removeKdigits(self, num, k):
        """
        :type num: str
        :type k: int
        :rtype: str
        """
        if k == len(num): return '0'
        nums = list(num)
        mins = []
        for i in range(k, -1, -1):
            if len(mins) == 0 or nums[i] <= mins[-1]:
                mins.append(nums[i])
        ret = ''
        for j in range(len(nums)-k):
            ret += mins[-1]
            mins.pop(-1)
            if k+j+1 < len(nums):
                while len(mins) > 0 and mins[0] > nums[k+j+1]:
                    mins.pop(0)
                mins.insert(0, nums[k+j+1])
        return str(int(ret))

Log in to reply
 

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