算法|算法：包含min函数的栈

文章图片

定义栈的数据结构，请在该类型中实现一个能够得到栈的最小元素的 min 函数在该栈中，调用 min、push 及 pop 的时间复杂度都是 O(1) 。
示例MinStack minStack = new MinStack();
minStack.push(-2);
minStack.push(0);
minStack.push(-3);
minStack.min(); --> 返回 -3.
minStack.pop();
minStack.top(); --> 返回 0.
minStack.min(); --> 返回 -2.
提示各函数的调用总次数不超过 20000 次
方法：辅助栈栈是一种后进先出（LIFO）的数据结构，为了满足题目的要求，我们建立了一个辅助栈用于存放最小值，核心思想就是：当每入栈一个值的时候，同时辅助栈存入最小值即可。
算法如下：

MinStack：分别初始化栈、辅助栈、以及存放到辅助栈最大值（用最大值占位，入栈的时候不需要判空处理）；
push：两个栈存值，注意辅助栈存值需要进行比对最小值；
pop：两个栈出栈
top：返回栈的头（新）元素
min：返回最小值，直接返回辅助栈的头元素即可

流程图说明：

代码如下：

复杂度分析

时间复杂度：对于题目中的所有操作，时间复杂度均为 O(1) 。因为栈的插入、删除与读取操作都是 O(1) ，我们定义的每个操作最多调用栈操作两次。
空间复杂度：O(n) ，其中 n 为总操作数。最坏情况下，我们会连续插入 n 个元素，此时两个栈占用的空间为 O(n) 。

END【算法|算法：包含min函数的栈】好兄弟可以点赞并关注我，全部都是干货。