设计一个栈,该栈可以进行push、pop、top和在常数时间内检索最小值的操作
方法1:引入minStack列表存放最小值,原生态的min()函数比较花费时间。
class MinStack(object):
def __init__(self):
self.stack = [] # 存放所有元素
self.minStack = [] # 存放每一次压入数据时,栈中的最小值
# (如果压入数据的值大于栈中的最小值就不需要重复压入最小值,
# 小于或者等于栈中最小值则需要压入)
def push(self, x):
self.stack.append(x)
if not self.minStack or self.minStack[-1] >= x:
self.minStack.append(x)
def pop(self): # 移除栈顶元素时,判断是否移除栈中最小值
if self.minStack[-1] == self.stack[-1]:
del self.minStack[-1]
self.stack.pop()
def top(self): #获取栈顶元素
return self.stack[-1]
def getMin(self): #获取栈中的最小值
return self.minStack[-1]
def all(self): #列表栈中所有的元素
return self.stack[:]
stack = MinStack()
stack.push(-2)
stack.push(0)
stack.push(-3)
stack.push(5)
stack.push(-4)
print('栈中所有元素:',stack.all())
print('最小元素:',stack.getMin())
stack.pop()
print('栈顶元素:',stack.top())
print('最小元素:',stack.getMin())
运行结果:
栈中所有元素: [-2, 0, -3, 5, -4]
最小元素: -4
栈顶元素: 5
最小元素: -3
方法2:用列表模拟栈,push、pop、top和getMin分别对应list.append()、list.pop()、list[-1]和min()操作
class MinStack(object):
def __init__(self):
self.stack = []
def push(self, x):
self.stack.append(x)
def pop(self):
if self.stack :
self.stack.pop()
def top(self):
if self.stack:
return self.stack[-1]
def getMin(self):
if self.stack:
return min(self.stack)
stack = MinStack()
stack.push(-2)
stack.push(0)
stack.push(-3)
stack.push(5)
stack.push(-4)
print(stack.getMin())
stack.pop()
print(stack.top())
print(stack.getMin())
运行结果:
-4
5
-3
参考博客:https://blog.csdn.net/qiubingcsdn/article/details/82561331