移掉 K 位数字（LeetCode 402）

文章目录

1.问题描述
2.难度等级
3.热门指数
4.解题思路
- 4.1 暴力法
- 4.2 贪心 + 单调栈
参考文献

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
}