Python 中的最小栈

这里我们将了解如何编写栈，它可以在常量时间内执行 push、pop、top 和检索最小元素。因此，函数为 push(x)、pop()、top() 和 getMin()

为此，我们将遵循以下步骤 −

• 初始化栈，其中最小元素为无穷大
• 对于 push 操作 push(x)
  • 如果 x < 最小值，则更新最小值 := x，
  • 将 x 推入栈中
• 对于 pop 操作 pop()
  • t := 顶部元素
  • 从栈中删除 t
  • 如果 t 为最小值，则最小值 := 栈中的顶部元素
• 对于 top 操作 top()
  • 直接返回顶部元素即可
• 对于 getMin 操作 getMin()
  • 返回最小元素

示例

让我们看看以下实现，以更好地理解 −

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

Arnab Chakraborty

更新于：2020 年 4 月 28 日

2K+ 浏览

开启你的 职业

完成课程后获得认证

开始