面试中算法（删去n个数字后的最小值）

 有一个整数，从该整数中去掉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)