有一个整数,从该整数中去掉n个数字,要求剩下的数字形成的新整数尽可能小。
分析:使用栈的特性,在遍历原整数的数字时,让所有数字一个一个入栈,当某个数字需要被删除时,(即栈顶数字>当前数字时,栈顶数字出栈(相当于删除))让该数字出栈。最后,程序把栈中的元素转化为字符串类型的结果。
如果整数num=541270936,n=3。如图所示:
# 以遍历数字作为外循环,以n作为内循环
def remove_n_digits2(num,n):
#新整数长度=原整数长度-n
nlen=len(num)-n
#创建一个栈
stack=[]
for i in range(len(num)):
#当前数字
curr=num[i]
#当栈顶数字>当前数字时,栈顶数字出栈(相当于删除)
while len(stack)>0 and stack[len(stack)-1]>curr and n>0:
stack.pop()
n-=1
# 如果遇到数字0,栈为空,0不入栈
if '0'==curr and len(stack)==0:
nlen-=1
if nlen<=0:
return '0'
continue
#遍历当前数字入栈
stack.append(curr)
#找到栈中第一个非零数字的位置
if nlen<=0:
return '0'
return ''.join(stack)
if __name__ == '__main__':
print(remove_n_digits2('18939477', 2)) # 139477
print(remove_n_digits2('39', 2)) # 0
print(remove_n_digits2('60800', 1)) # 800
print(remove_n_digits2('701312', 3)) # 11
print(remove_n_digits2('541270936', 3)) # 120936
时间复杂度是O(n)
文章评论