移位 K 位数（Leet 代码 402） - 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
}

---