Python 中的最小堆栈
pythonserver side programmingprogramming更新于 2025/10/31 14:36:17
在这里我们将看到如何创建一个堆栈，它可以在恒定时间内执行推送、弹出、顶部和检索最小元素。因此函数将是 push(x)、pop()、top() 和 getMin()
为了解决这个问题，我们将遵循以下步骤 −
- 通过将最小元素初始化为无穷大来初始化堆栈
- 对于推送操作 push(x)
- 如果 x < min，然后更新 min := x，
- 将 x 推入堆栈
- 对于弹出操作 pop()
- t := 顶部元素
- 从堆栈中删除 t
- 如果 t 是 min，则 min := 堆栈的顶部元素
- 对于顶部操作 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
相关文章
有用资源
python 参考教程 - 该教程包含有关 python 的更多信息:https://www.cainiaomax.com/python/
