Delete Digits

Question

Given string Arepresentative a positive integer which has N digits, remove any k digits of the number, the remaining digits are arranged according to the original order to become a new positive integer.

Find the smallest integer after remove k digits.

N <= 240 and k <= N,

Example Given an integer A = "178542", k = 4

return a string "12"

Thoughts

refer 解法

用stack, 然后找第一个递减的值。

跟next permutation很像。 从这个数的左边开始，找第一个递减的位置所在。

这道题，删掉一个数，相当于用这个数后面的数代替这个数。所以后面这个数一定要比当前小才行。所以找的是第一个递减的位置，把大的那个数删了。

Solution

class Solution:
    """
    @param A: A positive integer which has N digits, A is a string.
    @param k: Remove k digits.
    @return: A string
    """
    def DeleteDigits(self, A, k):
        # write you code here
        if not A or len(A) <= k:
            return ""

        stack = []
        deleteCount = 0
        for i in range(len(A)):
            cur = A[i]
            while stack and stack[-1] > cur and deleteCount < k:
                deleteCount += 1
                stack.pop()
            stack.append(cur)

        while deleteCount < k:
            stack.pop()
            deleteCount += 1

        result = []
        while stack:
            result.append(stack.pop())

        result.reverse()
        while len(result) > 0 and result[0] == "0":
            result.pop(0)

        return "".join(result)