当前位置: 首页 > 工具软件 > Poptop > 使用案例 >

设计一个支持 push,pop,top 操作,并能在常数时间内检索到最小元素的栈。

程志新
2023-12-01

设计一个支持 push,pop,top 操作,并能在常数时间内检索到最小元素的栈。

push(x) -- 将元素 x 推入栈中。
pop() -- 删除栈顶的元素。
top() -- 获取栈顶元素。
getMin() -- 检索栈中的最小元素。
class MinStack(object):
    def __init__(self):
        self.stack = []  # 存放所有元素
        self.minStack = []  
    def push(self, x):
        self.stack.append(x)
        if not self.minStack or self.minStack[-1] >= x:
            self.minStack.append(x)

    def pop(self):  # 移除栈顶元素时,判断是否移除栈中最小值
        if self.minStack[-1] == self.stack[-1]:
            del self.minStack[-1]
        self.stack.pop()

    def top(self):   #获取栈顶元素
        return self.stack[-1]

    def getMin(self): #获取栈中的最小值
        return self.minStack[-1]

    def all(self):  #列表栈中所有的元素
        return self.stack[:]

我们每次入栈的时候,保存的不再是真正的数字,而是它与当前最小值的差(当前元素没有入栈的时候的最小值)。 这样我们pop和top的时候拿到栈顶元素再加上上一个最小值即可。 另外我们在push和pop的时候去更新min,这样getMin的时候就简单了,直接返回min。

 类似资料: