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