高师本科化学实验教学体系建设与创新型人才培养 教学成果奖申报网站,wordpress如何添加首页描述,山东网站建设价格实惠,如何注册域名免费文章目录 1.问题描述2.难度等级3.热门指数4.解题思路4.1 暴力法4.2 贪心 单调栈 参考文献 1.问题描述
给你一个以字符串表示的非负整数 num 和一个整数 k#xff0c;移除这个数中的 k 位数字#xff0c;使得剩下的整数最小。请你以字符串形式返回这个最小的整数。
示例 1 … 文章目录 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 105num 仅由若干位数字0 - 9组成除了 0 本身之外num 不含任何前导零
2.难度等级
Medium。
3.热门指数
★★★★☆
出题公司富途。
4.解题思路
4.1 暴力法
对于两个相同长度的数字序列最左边不同的数字决定了这两个数字的大小因为高位的数字位权比低位的大。
例如 A1axxxB1bxxx如果 ab 则 AB。
基于此我们可以知道若要使得剩下的数字最小需要保证靠前的数字尽可能小。
所以每移除一个数字从左遍历找到第一个比右边大的数字移除即可。
如果找不到则移除最后一个数字即可。
循环上面的操作直到移除 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 : 0for ; j len(num)-1; j {if num[j] num[j1] {break}}num num[:j] num[j1:]}// 去除前导零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
}参考文献
402. 移掉 K 位数字 - LeetCode
