Remove K Digits
给你一个由数字组成的字符串形式的非负数 num，以及一个整数 k。恰好删除 k 位数字，并保持其余数字的原有顺序，使剩下的数字尽可能小。
以字符串形式返回结果，不要包含前导零。如果没有剩余数字，或剩下的全是零，则返回 "0"。
函数
- numstring
- 以数字字符串形式书写的数字
- kinteger
- 要删除多少位数字
- 返回值string
- 你可以保留的最小数字，以不带前导零的字符串形式表示
约束条件
1 ≤ num.length ≤ 4 × 1040 ≤ k ≤ num.lengthnum只包含数字0到9。num没有前导零，除非它本身就是数字"0"。
示例
- 输入
- num = "4325043"k = 3
- 输出
- "2043"
- 解释
- 删掉 4 和前面的第一个 3，就能让 2 移到最前面。0 不能放在最前面：它前面有四位数字，而你只能删除三位。最后一次删除会删掉 5，因为 5 在较小的 0 前面。
- 输入
- num = "30200"k = 1
- 输出
- "200"
- 解释
- 去掉 3 后得到
0200，去掉开头的 0 后就是200。去掉其他数字都会保留开头的 3，得到一个四位数，例如3000。
- 输入
- num = "52"k = 2
- 输出
- "0"
- 解释
- 两个数字都被移除了，所以什么都没剩下，答案是
"0"。
进阶
你会如何修改答案，删除 k 位数字，并留下最大的数？
提示
逐个打开提示，每个都会多透露一点。
无论用哪种方式移除
k位数字，剩下的数字位数都相同。对于两个位数相同的数字，第一个不同的位置决定了哪个数字更小。你应该优先让哪些数字尽可能小？从左边开始读取数字。第一次遇到某个数字大于它右边紧接着的数字时，删除这个数字，就能尽可能早地降低数值。如果数字始终没有递减，就删除最后一位数字。
把你决定保留的数字放在栈中。推入新数字之前，只要还有可删除的次数，就从栈顶弹出所有更大的数字。最后，从栈顶取出剩余可删除的数字，然后去掉前导零。
题解
最左边的数字权重最大，因此第一个比右侧相邻数字大的数字应该删掉。把保留的数字依次放入栈中，就能用一次遍历将这条规则应用于整个字符串。最后剩余要删除的数字从末尾移除，并在最后去掉前导零。
每次删除一位数字
结果正确，但无法在最大的测试中运行完毕
思路
每次删除一位数字：找到第一个满足 num[i] > num[i+1] 的位置 i，并删除 num[i]；如果数字始终没有下降，就删除最后一位。重复 k 次。
每个答案都保留 n-k 位数字，因此，两个答案第一次出现不同的位置决定了哪个更小。在 i 之前，数字始终没有下降，所以删除更早的一位会让一位至少同样大的数字移到当前位置；删除更晚的一位则会让较大的 num[i] 留在原位。删除 num[i] 可以降低最早能降低的位置上的数字。
每次删除后，都会从左侧重新扫描，并将后面的数字向前移动，因此工作量为 O(n·k)。对于由 40,000 个 1 组成的数字，且 k = 25,000，扫描会读取约 6.9 × 10^8 位数字。
算法
- 把这些数字复制到一个可以从中删除元素的列表中。
- 重复
k次：从左侧开始，找到第一个大于下一个数字的数字；如果没有，就走到最后一个数字，然后删除它。 - 去掉前导零，如果没有剩余内容，就返回
"0"。
def removeKdigits(num, k):
digits = list(num)
for _ in range(k):
# Find the first digit that is bigger than the digit after it.
# If the digits never go down, i stops on the last digit.
i = 0
while i + 1 < len(digits) and digits[i] <= digits[i + 1]:
i += 1
del digits[i]
result = "".join(digits).lstrip("0")
return result if result else "0"保留数字的单调栈
思路
慢速版本删除 num[i] 后，i 前面的数字仍然不会变小，所以接下来只能从空位前面的数字开始删除。用一个栈保存这段前缀，也就是保留下来的数字，并确保它们从栈底到栈顶始终不递减。遇到比栈顶小的新数字时，栈顶数字比它右边的邻居大，也就是慢速版本会删除的那个数字。弹出栈顶，消耗一次删除次数；只要新的栈顶仍然更大，就继续弹出。
对于 4325043，当 k = 3 时，3 会弹出 4，2 会弹出 3，0 会弹出 5。4 和 3 依次入栈，得到 2043。
每个数字只入栈一次，每次弹出都会消耗 k 次删除中的一次，因此这次遍历的复杂度为 O(n)。
算法
- 创建一个空的数字栈。
- 遍历
num的每一位数字：只要还有可删除的数字，并且栈顶数字大于当前数字，就弹出栈顶数字，并用掉一次删除机会。然后将当前数字压入栈中。 - 如果循环结束后还有可删除的数字，就从栈顶删除相应数量的数字。
- 从栈底到栈顶读取栈中的数字，跳过前导零，然后返回剩余部分；如果没有剩余数字，则返回
"0"。
def removeKdigits(num, k):
stack = [] # kept digits, never decreasing from bottom to top
for digit in num:
# A bigger digit right before a smaller one: dropping it makes the number smaller.
while k > 0 and stack and stack[-1] > digit:
stack.pop()
k -= 1
stack.append(digit)
# The kept digits never decrease, so any removals left come off the end.
stack = stack[:len(stack) - k]
result = "".join(stack).lstrip("0")
return result if result else "0"
易错点和边界情况
- 当栈顶与新数字相等时弹出元素。在
112中，k = 1时会留下12；正确答案是11。 - 忘记在循环后处理剩余的删除次数，或者从开头删除。栈的长度不会减少，因此最后的数字会是：
123456789中，k = 3时会得到123456。 - 把去掉的零也算作删除次数。在
100200中，k = 1时，唯一删除的数字是 1；前面的零会免费去掉，答案是200。 - 返回空字符串。
10中，k = 1时只剩一个零，因此答案是"0"。 - 把
num转换成整数。它可能有4 × 10^4位，远超任何整数类型的范围，因此要把数字作为字符进行比较。
常见问题3
Remove K Digits 的时间复杂度是多少？
使用单调栈处理 n 位数字，时间复杂度为 O(n)：每位数字只会入栈一次，每次弹出都会消耗一次 k 次删除机会。栈最多存放 n 位数字，因此额外空间复杂度为 O(n)。每次删除都从左侧重新扫描，时间复杂度为 O(n·k)。
在 Remove K Digits 中，如何处理前导零？
先删除数字，然后只去掉末尾的零。前面的零不会改变数值，所以不需要删除：10200 在 k = 1 时变成 0200，然后变成 200。如果去掉零后什么都不剩，就返回 "0"。
Can Remove K Digits 能用 O(1) 的额外空间解决吗？
可以，前提是你可以修改输入。栈中保存的数字不会超过已读取的数字，因此可以直接放在数字数组的前面，并用一个索引表示栈顶。字符串不可变的语言仍需要复制一份数字，空间复杂度为 O(n)。
相似题目
运用相同思路的题目。做两三道，才能真正掌握一种模式。
def removeKdigits(num, k):
# 在这里编写代码测试 #1
测试 #2
测试 #3
参数
num = "4325043" k = 3
预期输出
"2043"