Python中的最小堆栈

在这里，我们将看到如何制作一个堆栈，该堆栈可以在恒定时间内执行推，弹出，顶和检索min元素。因此，函数将是push(x)，pop()，top()和getMin()

为了解决这个问题，我们将遵循以下步骤-

• 通过min元素将堆栈初始化为无穷大

• 对于推送操作push(x)

• 如果x <min，则更新min：= x，

• 将x推入堆栈

• 对于弹出操作pop()

• t：=顶部元素

• 从堆栈中删除t

• 如果t为min，则min：=堆栈的顶部元素

• 对于top操作top()

• 只需返回顶部元素

• 对于getMin操作getMin()

• 返回min元素

示例

让我们看下面的实现以更好地理解-

class MinStack(object):
   min=float('inf')
   def __init__(self):
      self.min=float('inf')
      self.stack = []
   def push(self, x):
      if x<=self.min:
         self.stack.append(self.min)
         self.min = x
      self.stack.append(x)
   def pop(self):
      t = self.stack[-1]
      self.stack.pop()
      if self.min == t:
         self.min = self.stack[-1]
         self.stack.pop()
   def top(self):
      return self.stack[-1]
   def getMin(self):
      return self.min
m = MinStack()
m.push(-2)
m.push(0)
m.push(-3)
print(m.getMin())
m.pop()
print(m.top())
print(m.getMin())

输入值

m = MinStack()
m.push(-2)
m.push(0)
m.push(-3)
print(m.getMin())
m.pop()
print(m.top())
print(m.getMin())

输出结果

-3
0
-2