#43. Push, Pop, GetMin

Push, Pop, GetMin

题目描述

维护一个初始为空的栈,支持 push、pop、top 和 min。四种操作均应在 O(1) 时间完成;min 返回栈内最小值。

输入格式

第一行整数 q(1≤q≤100000)。随后 q 行,每行是 push x、pop、top 或 min。x 为绝对值不超过 10^9 的整数。保证 pop、top、min 操作时栈非空。

输出格式

对每次 top 或 min 操作输出一行整数。push 和 pop 不输出。

示例

8
push -1
push 2
min
top
pop
push 1
top
min
-1
2
1
-1

接口说明

原书 Push, Pop, GetMin / AcWing41 为类接口题。本包使用上述标准输入输出适配,算法要求不变。测试数据为补生成。