题目描述
实现一个特殊功能的栈,在实现栈的基本功能的基础上,再实现返回栈中最小元素的操作。
输入描述:
第一行输入一个整数N,表示对栈进行的操作总数。
下面N行每行输入一个字符串S,表示操作的种类。
如果S为"push",则后面还有一个整数X表示向栈里压入整数X。
如果S为"pop",则表示弹出栈顶操作。
如果S为"getMin",则表示询问当前栈中的最小元素是多少。
输出描述:
对于每个getMin操作,输出一行表示当前栈中的最小元素是多少。
示例1
输入
复制
6
push 3
push 2
push 1
getMin
pop
getMin
输出
复制
1
2
备注:
1<=N<=1000000
-1000000<=X<=1000000
数据保证没有不合法的操作
解法:
class Stack():
def __init__(self):
self.L = []
self.minL = []
def isEmpty(self):
return self.L == []
def isminLEmpty(self):
return self.minL == []
def push(self,x):
self.L.append(x)
if self.isminLEmpty() or x < self.minL[-1]:
self.minL.append(x)
def pop(self):
a = self.L.pop()
if not self.isminLEmpty() and self.minL[-1] == a:
self.minL.pop()
def getMin(self):
if not self.isminLEmpty():
return self.minL[-1]
if __name__ == '__main__':
S = Stack()
N = int(input())
for _ in range(N):
l = input().split()
if l[0] == 'push':
S.push(int(l[1]))
elif l[0] == 'pop':
S.pop()
else:
print(S.getMin())


京公网安备 11010502036488号