最小栈
已关闭dadingPython / C++入场费 2 金币2 次提交
题目描述
实现一个最小栈,支持以下操作:
- push x — 将整数 x 压入栈中
- pop — 弹出栈顶元素
- top — 返回栈顶元素的值
- getMin — 返回栈中最小元素的值
所有操作都必须在 O(1) 时间复杂度内完成。初始时栈为空,保证 pop、top、getMin 操作时栈不为空。
输入格式
第一行一个整数 n,表示操作次数。 接下来 n 行,每行一个操作:
- push x:压入整数 x
- pop:弹出栈顶
- top:输出栈顶元素
- getMin:输出栈中最小元素
输出格式
对于每个 top 和 getMin 操作,各输出一行对应的结果。
输入输出样例
样例 1
输入:
8 push 5 push 3 getMin push 7 getMin top pop getMin
输出:
3 3 7 5
说明/提示
考虑使用辅助栈来跟踪最小值,每次 push 和 pop 时同步更新。