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

曾经终败给现在 2024-05-28 10:22 58阅读 0赞

#### **有一个整数，从该整数中去掉n个数字，要求剩下的数字形成的新整数尽可能小。** ####

> 分析：使用栈的特性，在遍历原整数的数字时，让所有数字一个一个入栈，当某个数字需要被删除时，（即栈顶数字>当前数字时，栈顶数字出栈（相当于删除））让该数字出栈。最后，程序把栈中的元素转化为字符串类型的结果。

> #### **如果整数num=541270936，n=3。如图所示：** ####

![984a0d9e9c574654aaa9a16219573893.png][]

![c8185ccb19e140b7bc5c231977f37335.png][]

# 以遍历数字作为外循环，以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)

[984a0d9e9c574654aaa9a16219573893.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/05/28/98350dca315b44edafea7c95bff576c6.png
[c8185ccb19e140b7bc5c231977f37335.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/05/28/174ef241964c4e37972a37c89474a310.png