有一个整数，从该整数中去掉n个数字，要求剩下的数字形成的新整数尽可能小。
分析：使用栈的特性，在遍历原整数的数字时，让所有数字一个一个入栈，当某个数字需要被删除时，（即栈顶数字>当前数字时，栈顶数字出栈（相当于删除））让该数字出栈。最后，程序把栈中的元素转化为字符串类型的结果。
如果整数num=541270936，n=3。如图所示：
# 以遍历数字作为外循环，以n作为内循环
def remove_n_digits2(num,n):#新整数长度=原整数长度-nnlen=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-=1if 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)) # 139477print(remove_n_digits2('39', 2)) # 0print(remove_n_digits2('60800', 1)) # 800print(remove_n_digits2('701312', 3)) # 11print(remove_n_digits2('541270936', 3)) # 120936时间复杂度是O(n)
