移掉 K 位数字（LeetCode 402）
1.问题描述
给你一个以字符串表示的非负整数 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 <= 105
- num 仅由若干位数字（0 - 9）组成
- 除了 0 本身之外，num 不含任何前导零
2.难度等级
Medium。
3.热门指数
★★★★☆
出题公司：富途。
4.解题思路
4.1 暴力法
对于两个相同长度的数字序列，最左边不同的数字决定了这两个数字的大小，因为高位的数字位权比低位的大。
例如 A=1axxx，B=1bxxx，如果 a>b 则 A>B。
基于此，我们可以知道，若要使得剩下的数字最小，需要保证靠前的数字尽可能小。
所以每移除一个数字，从左遍历，找到第一个比右边大的数字，移除即可。
如果找不到，则移除最后一个数字即可。
循环上面的操作，直到移除 K 位数字。
我们以 4258 为例，如果要求我们删除两个数字。
第一次遍历，找到第一个大于右边的数字，为 4，所以删除 4 剩下 258。
第二次遍历，直到最后一个数字，也没有找到，所以删除最后一个数字 8 即可。
剩下 25 便是最小数。
这里需要注意，剩下的数不能有前导零。比如 108 删除一位数字，那么删除 1 后，最终返回前需要将前导 0 去掉。
时间复杂度：
每次遍历找到第一个大于右边的数字时间复杂度是 O(n)，需要遍历 k 次，所以总的时间复杂度是 O(nk)。
空间复杂度： O(1)。
下面以 Go 给出实现示例。
func removeKdigits(num string, k int) string {
// 遍历 k 次找到第一个大于右边相邻的数字并移除
for i := 0; i < k; i++ {
j := 0
for ; j < len(num)-1; j++ {
if num[j] > num[j+1] {
break
}
}
num = num[:j] + num[j+1:]
}
// 去除前导零
num = strings.TrimLeft(num, "0")
if num == "" {
return "0"
}
return num
}4.2 贪心 + 单调栈
其实，最小的数有一个特点，就是小的数字在高位（左边），大的数字在低位（右边），比如 123 小于 321。
所以最小的数的数字应该是单调不降的，删除的 k 位数字都尽可能的在高位（左边）寻找。
考虑从左往右增量的构造最后的答案，我们可以用一个栈维护当前的答案序列。
栈中的元素代表截止到当前位置，删除不超过 k 次个数字后，所能得到的最小整数。根据之前的讨论：「在删除 k 个数字之前，栈中的序列从栈底到栈顶单调不降」。
因此，对于每个数字，如果该数字小于栈顶元素，我们就不断地弹出栈顶元素，直到
- 栈为空
- 或者新的栈顶元素不大于当前数字
- 或者我们已经删除了 k 位数字
然后入栈。
如果已经删除了 k 位数字，那么将栈中数字与剩余数字拼接，去掉前导零后返回。
如果还没有删除 k 位数字，则继续遍历后面的数字直到遍历完。
最后栈中的数字是「单调不降」，所以弹出剩余未删除的数字后，去掉前导零后返回即可。
时间复杂度： 遍历一次整数即可，所以时间复杂度是 O(n)。
空间复杂度：需要一个单调栈存储已经遍历的数字序列，所以空间复杂度是 O(n)。
下面以 Go 为例给出实现。
func removeKdigits(num string, k int) string {
var stack []byte
// 遍历数字
for i := range num {
// 出栈
for k > 0 && len(stack) > 0 && stack[len(stack)-1] > num[i] {
stack = stack[:len(stack)-1]
k--
}
// 入栈
stack = append(stack, num[i])
}
stack = stack[:len(stack)-k]
// 去除前导零
num = strings.TrimLeft(string(stack), "0")
if num == "" {
return "0"
}
return num
}