最小栈

已关闭
dadingPython / C++入场费 2 金币2 次提交

题目描述

实现一个最小栈,支持以下操作:

  1. push x — 将整数 x 压入栈中
  2. pop — 弹出栈顶元素
  3. top — 返回栈顶元素的值
  4. 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 时同步更新。