难度: Medium
给你一个以字符串表示的非负整数 num 和一个整数 k ，移除这个数中的 k 位数字，使得剩下的数字最小。请你以字符串形式返回这个最小的数字。
示例 1 ：
输入：num = "1432219", k = 3 输出："1219" 解释：移除掉三个数字 4, 3, 和 2 形成一个新的最小的数字 1219 。
示例 2 ：
输入：num = "10200", k = 1 输出："200" 解释：移掉首位的 1 剩下的数字为 200. 注意输出不能有任何前导零。
示例 3 ：
输入：num = "10", k = 2 输出："0" 解释：从原数字移除所有的数字，剩余为空就是 0 。
提示：
1 <= k <= num.length <= 105num 仅由若干位数字（0 - 9）组成num 不含任何前导零运行时间: 30 ms
内存: 17.3 MB
class Solution:
def removeKdigits(self, num: str, k: int) -> str:
l = len(num)
if l == k:
return '0'
stack = []
remain = l - k
for i in num:
while stack and k and i < stack[-1]:
k -= 1
stack.pop()
stack.append(i)
return ''.join(stack[:remain]).lstrip('0') or '0'
这个题解使用了贪心算法和单调栈的思路。我们从左到右遍历数字，对于每个数字，如果当前数字小于栈顶元素，则弹出栈顶元素，直到栈为空或者栈顶元素小于等于当前数字。这样可以保证栈中的元素是单调递增的。最后，我们取出栈中前 remain 个元素作为结果，其中 remain 为原数字长度减去要删除的数字个数 k。
时间复杂度: O(n)
空间复杂度: O(n)
class Solution:
def removeKdigits(self, num: str, k: int) -> str:
l = len(num)
if l == k:
return '0'
stack = []
remain = l - k
for i in num:
# 如果当前数字小于栈顶元素，则弹出栈顶元素
while stack and k and i < stack[-1]:
k -= 1
stack.pop()
stack.append(i)
# 取出栈中前 remain 个元素作为结果
return ''.join(stack[:remain]).lstrip('0') or '0'
在遍历数字时，执行出栈操作的目的是为了保持栈的单调递增性，从而确保最终得到的数字是尽可能小的。当当前数字小于栈顶元素时，移除栈顶元素可以去掉一个较大的数字，使得之后加入的较小数字能够更靠前，这样不仅减少了数字的总体大小，而且有效地利用了可以删除的数字个数的限制。因此，这种操作有助于实现贪心策略，即每步尽可能保持结果数字的最小性。
如果后面的数字和栈顶元素相等，算法不需要特别的处理，因为在这种情况下，无论保留哪一个数字结果都是相同的。栈的目的是保持递增顺序而非递减，因此相等的情况并不会违反这一规则。保留栈顶元素还是后面的数字对最终的结果没有影响，因为它们的数值是一样的，所以算法简单地选择继续保留栈顶的元素，而后面的数字只是简单地追加在后面。
代码中的`lstrip('0') or '0'`处理是为了去除数字字符串左侧可能出现的前导零。在移除某些数字后，尤其是最高位的数字后，可能会产生前导零，这会影响数字的正常表达。例如，从'10200'中移除一位得到'0200'，经过`lstrip('0')`后变为'200'。这个处理确保了得到的结果是一个有效的数字表达。如果结果字符串全部是零，则`lstrip('0')`会返回一个空字符串，这时通过`or '0'`确保输出至少为'0'，正确表示数值零。
如果输入的数字已经是最小可能值，例如'12345'，并且需要移除'k'个数字，那么算法会依然按照流程执行，但是实际上不会进行出栈操作。因为每个后续的数字都大于前一个数字，栈顶元素永远不会大于当前考虑的数字，因此栈内数字始终保持单调递增。在这种情况下，算法最终简单地移除尾部的'k'个数字，因为这是保持数字最小的唯一方式。结果就是按照从左到右保留前'n-k'个数字。