题解 | #移掉 K 位数字#
移掉 K 位数字
http://www.nowcoder.com/practice/0fe685c8272d40f1b9785fedd2499c1c
题目分析
- 题目给出了我们一个数字字符串,和一个数字k
- 题目说我们可以从字符串中去掉k位数字,返回最小数字字符串的方案
方法一:单调栈
- 实现思路
- 我们需要维护一个单调栈,将数字字符串每一个元素进行入栈处理(在这里我们用列表表示单调栈)
- 当取到的数字字符大于栈顶的时候,我们让数字正常入栈
- 当取到的数字字符小于栈顶的时候,我们就将栈顶元素出栈,并且一直比较新的栈顶元素,直到栈顶元素与取得元素相等或更小为止
- 出栈则说明我们去掉这个数字字符,相应k的值就需要自减
#
# 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
#
#
# @param num string字符串
# @param k int整型
# @return string字符串
#
class Solution:
def removeKnums(self , num: str, k: int) -> str:
# write code here
stack = []
for c in num:
while stack and k and int(c) < int(stack[-1]): # 维护单调栈的单调性
k -= 1
stack.pop()
if not stack and c == '0': # 如果现在stack开头的全是0就直接跳过
continue
stack.append(c)
stack = stack[:-k] if k else stack
if not stack: # 如果最后一个数也不剩下就说明应该结果是0
stack.append('0')
return ''.join(stack) # 返回字符串形式
复杂度分析
- 时间复杂度:,一趟遍历的时间代价
- 空间复杂度:,开辟的栈空间的开销
方法二:贪心
- 实现思路
- 如果要剩下的数字最小,那么数字从左开始的每一位都要尽可能地小,因此我们要从剩余数字的高位开始,在有效范围内找到最小的数字。
有效范围:对于
num = "1432219", k = 3
,要求删除 3 位数字,留下 4 位数字。那么第 1 位数字的查找有效范围是 1432,即下标 0 ~ 3。因为如果我们再往后选择,比如选择第 5 位数字 2,那么我们就无法完整地凑齐 4 位数字了。假设我们要从长度为 length 的字符串 num 中删除 k 位数字,那么第 x 个数字的有效查找范围是下标x-1 ~ k+x-1
- 整体思路是:
-
从高位开始逐一查找每一位数字尽可能小的取值。其中,第 x 位数字的有效取值范围是 x-1 ~ k+x-1
-
找到最小值后记录最小值 min_num 以及对应的下标 min_index
-
设置下一轮的查找开始位置为 min_index + 1
-
循环此过程,直到完成所有数字的查找
-
#
# 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
#
#
# @param num string字符串
# @param k int整型
# @return string字符串
#
class Solution:
def removeKnums(self , num: str, k: int) -> str:
# write code here
num_length = len(num)
if num_length <= k:
return "0"
left_count = num_length - k
res = ""
count = 0
begin = 0
while count < left_count:
min_index = 0
min_num = float('inf')
for i in range(begin, k + count + 1):
# 找到最小数
if int(num[i]) < min_num:
min_index = i
min_num = int(num[i])
# 把找到的最小数加入结果列表
res += str(min_num)
# 设置下一轮查找范围的起点
begin = min_index + 1
count += 1
return "0" if len(res) == 0 else str(int(res))
复杂度分析
- 时间复杂度:,最差的时间代价与k值有关,因此用表示
- 空间复杂度:,只引入常量级别的空间开销