[数据结构][Python][经典题目]最小栈实现

我不是女神ヾ 2022-10-02 12:51 187阅读 0赞

# 题目 #

实现一个栈，该栈带有出栈pop、入栈push、取最小元素3个方法。要保证这3个方法的时间复杂度都是O(1)

调用getMin方法，返回最小值3

# 解题步骤 #

1、设原有的栈叫做栈A，此时创建一个额外的“备胎”栈B，用于辅助栈A

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

3、之后，每当新元素进入栈A时，比较新元素和栈A当前最小值的大小，如果小于栈A当前最小值，则让新元素入栈B，此时栈B的栈顶元素就是栈A当前最小值

5、当调用getMin方法时，返回栈B的栈顶所存储的值，这也是栈A的最小值。  
时间复杂度O(1),最坏情况空间复杂度是O(n)

class MinStack(object):
        def __init__(self):
            """
            initialize your data structure here.
            """
            self.stack = []
            self.min = None
    
        def push(self, x):
            """
            :type x: int
            :rtype: void
            """
            self.stack.append(x)
            if self.min == None or self.min > x:
                self.min = x
    
        def pop(self):
            """
            :rtype: void
            """
    
            popItem = self.stack.pop()
            if len(self.stack) == 0:
                self.min = None
                return popItem
    
            if popItem == self.min:
                self.min = self.stack[0]
                for i in self.stack:
                    if i < self.min:
                        self.min = i
            return popItem
    
        def top(self):
            """
            :rtype: int
            """
            return self.stack[-1]
    
        def getMin(self):
            """
            :rtype: int
            """
            return self.min
    if __name__ == '__main__':
        minstack = MinStack()
        minstack.push(4)
        minstack.push(9)
        minstack.push(7)
        minstack.push(3)
        minstack.push(8)
        minstack.push(5)
        mins = minstack.getMin()
        print("mins:",mins)
        minstack.pop()
        minstack.pop()
        minstack.pop()
        tops =minstack.top()
        print("tops:",tops)
        minm = minstack.getMin()
        print("minm:",minm)
    output:
    mins: 3
    tops: 7
    minm: 4