最小栈

题解思路

这道题要求实现一个栈（Stack），并在常数时间内（$O(1)$）获取栈中的最小值。由于栈的基本操作（push、pop、top）都是 $O(1)$ 的，我们的目标是保证 getMin 也能达到 $O(1)$ 的复杂度。

方法：辅助栈

思路：
我们使用两个栈：

Leetcode 70.最小栈-原题链接

题目内容

设计一个支持 $push$ ，$pop$ ，$top$操作，并能在常数时间内检索到最小元素的栈。

实现 $MinStack$ 类:

• $MinStack()$ 初始化堆栈对象。

• $void push(int val)$ 将元素val推入堆栈。

• $void pop()$ 删除堆栈顶部的元素。

• $int top()$ 获取堆栈顶部的元素。

• $int getMin()$ 获取堆栈中的最小元素。

输入描述

输入包含多行：

• 第一行是一个整数 n，表示操作次数
• 接下来的 n 行，每行包含一个操作：
  • "push x" (x 是整数)：将 x 推入栈
  • "pop"：弹出栈顶元素
  • "top"：获取栈顶元素
  • "getMin"：获取栈中最小元素

输出描述

对于每个 "top" 和 "getMin" 操作，输出对应的结果（每行一个整数）。其他操作无需输出。

样例1

输入

7
push -2
push 0
push -3
getMin
pop
top
getMin

输出

-3
0
-2

说明

• MinStack minStack = new MinStack();
• minStack.push(-2); // 栈：[-2]
• minStack.push(0); // 栈：[-2, 0]
• minStack.push(-3); // 栈：[-2, 0, -3]
• minStack.getMin(); // 返回 -3
• minStack.pop(); // 栈：[-2, 0]
• minStack.top(); // 返回 0
• minStack.getMin(); // 返回 -2

提示

• $-2^{31} <= val <= 2^{31} - 1$
• $pop$、$top$ 和 $getMin$操作总是在非空栈上调用
• $push$, $pop$, $top$, $and\ getMin$最多被调用 $3 * 10^4$ 次