数据结构
网络
RDBMS
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化学
生物
数学
英语
经济学
心理学
社会研究
时尚研究
法律研究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
更新于：2020 年 4 月 28 日
2K+ 浏览
广告