面试中算法(最小栈）

墨蓝 2024-05-28 10:21 155阅读 0赞

## 最小栈的实现 ##

实现一个栈，该栈有出栈(pop）、入栈(push)、取最小元素(get\_min) 。要保证时间复杂度都是O (1）。

![fd512ea7259e499bbc4b6cdff0b775ec.png][]

**第1步**：设原有的栈叫作栈A，额外的“备胎”栈B，用于辅助栈A。

当第1个元素进入栈A时，让新元素也进入栈 B。这个唯一的元素是栈A的当前最小值。

![95ea05e398534ecaa85537158ec680e8.png][]

**第2步**：每当新元素进入栈A时，比较新元素和栈A当前最小值的大小，如果小于栈A当前最小值，则让新元素进入栈B，此时栈B的栈顶元素就是栈A当前最小值。

![f8e73aea609840f7b78ee8b6b76ea1f6.png][]

**第3步**：每当栈A有元素出栈时，如果出栈元素是栈A当前最小值，则让栈B的栈顶元素也出栈。此时栈B余下的栈顶元素所指向的是栈A中原本第2小的元素，代替刚才的出栈元素成为栈A的当前最小值。（备胎转正。)

![d333a303d2af4e919155385bd59a1c43.png][]

第4步：当调用get\_min方法时，返回栈B的栈顶所存储的值，这也是栈A的最小值。

class  StackMin:
        def __init__(self):
            '''
            初始化 栈A，栈B
            '''
            self.stack_a=[]
            self.stack_b=[]
    
        def push(self,newele):
            '''入栈'''
             #入栈A
             self.stack_a.append(newele)
             # 若栈B为空，或新元素的值小于或等于栈B栈顶元素的值，
             if len(self.stack_b)==0 or newele<=self.stack_b[len(self.stack_b)-1]:
                 # #将新元素压入栈B
                 self.stack_b.append(newele)
    
        def pop(self):
            '''出栈'''
            # 如果栈A出栈元素和栈B栈顶元素的值相等，栈B的栈顶元素出栈
            if self.stack_a[len(self.stack_a)-1]==self.stack_b[len(self.stack_b)-1]:
                self.stack_b.pop()   #出栈
            return self.stack_a.pop() #出栈
    
        def get_min(self):
            #判断栈A为空
            if(self.stack_a==0):
                return None
            #返回栈B的最小值
            return self.stack_b[len(self.stack_b)-1]
    
    
    if __name__ == '__main__':
        #对象
        stack=StackMin()
        #入栈5，8，6，3，2，9
        stack.push(5)
        stack.push(8)
        stack.push(6)
        stack.push(3)
        stack.push(2)
        stack.push(9)
        print(stack.get_min())
        #出栈
        stack.pop() #2
        # stack.pop()  #3
        # stack.pop()  #5
        print(stack.get_min())

> 显然进栈、出栈、取最小值的**时间复杂度都是O（1)**，最坏情况空间复杂度是O(n)。

[fd512ea7259e499bbc4b6cdff0b775ec.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/05/28/dea9ed2cfed343a3a3a2a8088f0fb03c.png
[95ea05e398534ecaa85537158ec680e8.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/05/28/bbcb0b204e664c839799de57c645dad3.png
[f8e73aea609840f7b78ee8b6b76ea1f6.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/05/28/f517aed21bed4f1d84e6b20e6485c9cf.png
[d333a303d2af4e919155385bd59a1c43.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/05/28/4256d90359e5499e8ea6598cd76f9d9a.png