402. 移掉 K 位数字

题目链接：https://leetcode-cn.com/problems/remove-k-digits/
难度：中等

描述：
给你一个以字符串表示的非负整数 num 和一个整数 k ，移除这个数中的 k 位数字，使得剩下的数字最小。请你以字符串形式返回这个最小的数字。

提示：
1 <= k <= len(num) <= 100000
除非num == "0"，num不含前导"0"。

题解

从前往后遍历，我们应该尽可能保留较小的数组，放弃较大的数字

class Solution(object):
    def removeKdigits(self, num, k):
        stack = []
        ret_len = len(num) - k
        for digit in num:
            while k and stack and stack[-1] > digit:
                stack.pop()
                k -= 1
            stack.append(digit)
        # 防止k > 0及没有剩下数字
        return ''.join(stack[:ret_len]).lstrip('0') or '0'