题目描述
实现一个特殊功能的栈,在实现栈的基本功能的基础上,再实现返回栈中最小元素的操作。
输入描述:
第一行输入一个整数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())