亚马逊面试题：带最小值操作的栈 · Min Stack

LintCode（炼码） / LeetCode 参考答案免费查询
描述中文
实现一个栈, 支持以下操作:
push(val) 将 val 压入栈pop() 将栈顶元素弹出, 并返回这个弹出的元素min() 返回栈中元素的最小值
要求 O(1) 开销

保证栈中没有数字时不会调用 min()

在线评测地址：
LintCode 炼码
样例
样例 1：输入：

push(1)
min()
push(2)
min()
push(3)
min()

输出：

1
1
1

题解思路
使用两个仅支持 pop 和 push 的栈就可以完成, stack 储存压入的数据, minStack 储存最小值.
push 直接把元素压入 stack, 对于 minStack, 如果它为空则直接压入, 反之压入当前元素与 minStack 栈顶的最小值pop 两个栈都弹出一个元素, 返回 stack 弹出的元素min 返回 minStack 的栈顶

还可以令 minStack 为单调栈, 即

亚马逊面试题：带最小值操作的栈 · Min Stack最先出现在Python成神之路。