[数据结构与算法]LeetCode 402. Remove K Digits - 单调栈（Monotonic Stack）系列题8

Given string num representing a non-negative integer?num, and an integer?k, return?the smallest possible integer after removing?k?digits from?num.

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.

Constraints:

• 1 <= k <= num.length <= 105
• num?consists of only digits.
• num?does not have any leading zeros except for the zero itself.

题目给定一个字符串num和一个整数k，字符串num的长度为n用来表示一个n位的整数，其中每个字符的范围为‘0’~‘9’表示整数每一位上的数字。现在要求删掉其中k个字符后，使剩下的字符表示的整数最小。

要一串字符表示的整数最小，那就要尽可能地使小的字符在前（即高位）大的字符在后，也就是说尽可能使字符递增排列。因此要是用一个堆栈来依次存放字符那就要尽可能使堆栈保持单调递增。

定义一个堆栈，遍历字符串，如果当前字符比栈顶的字符大也就比单调递增栈里的所有字符大，那么该字符直接入栈；如果当前字符比栈顶的字符小，那说明删除前面大的字符（即高位大的字符）可以使得最后的整数更小，因此可以把栈里比当前字符大的字符全弹出栈删掉，但是由于只能删除k个字符，每弹出一个字符k就要减1，当k等于0时表示不能再删字符，这时即使栈里还有更大字符也不能再删了。最后把当前字符压入栈，有一种特殊情况，要是当前字符为0栈为空，由于整数最高位不能为0，因此该‘0’字符可以直接丢弃不入栈（这种情况不算删除所以k不用减1）。

遍历完数组后有可能k还大于0，说明还没删够k个字符，因此还得继续删除直到k为0或者栈为空。最后栈里剩下的字符就是删除k个字符后可以表示的最小整数，要是栈为空答案为0。

class Solution:
    def removeKdigits(self, num: str, k: int) -> str:
        st = []
        
        for i in range(len(num)):
            while st and st[-1] > num[i] and k > 0:
                st.pop()
                k -= 1
            if not st and num[i] == '0':
                continue
            st.append(num[i])
            
        while k > 0 and st:
            st.pop()
            k -= 1
            
        return ''.join(st) if st else '0'