阿Q的博客

[402] Remove K Digits

https://leetcode.com/problems/remove-k-digits/description/

algorithms
Medium (25.61%)
Source Code: 402.remove-k-digits.py
Total Accepted: 57K
Total Submissions: 216.1K
Testcase Example: '"1432219"\n3'

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.

python

# coding: utf-8
class Solution(object):
    def removeKdigits(self, num, k):
        """
        :type num: str
        :type k: int
        :rtype: str
        """
        lenc = len(num)
        if not num or lenc <= k: return '0'

        stack = []
        for i in range(lenc):
            if not stack:
                stack.append(num[i])
            else:
                # print('stack, len, need, last, current', stack, len(stack)+lenc-(i+1), lenc-k, stack[-1], num[i])
                while stack and len(stack) + lenc - (i+1) >= lenc - k and int(stack[-1]) > int(num[i]):
                    stack.pop(-1)
                stack.append(num[i])
        return ''.join(stack[0:lenc-k]).lstrip('0') or '0'


# s = Solution()
# print s.removeKdigits('1432219', 3)
# print s.removeKdigits('112', 1)