Python中的最小堆栈

  • Z时代
  • 2024-01-10
  • 分类：综合

在这里，我们将看到如何制作一个堆栈，该堆栈可以在恒定时间内执行推，弹出，顶和检索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

以上是 Python中的最小堆栈 的全部内容， 来源链接： utcz.com/z/327230.html

回到顶部