一、题目
定义栈的数据结构，请在该类型中实现一个能够得到栈的最小元素的 min 函数在该栈中，调用 min、push 及 pop 的时间复杂度都是 O(1) 。
二、示例
2.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次
三、解题思路
3.1> 维护不完整的有序栈
根据题目描述，我们需要定义一个栈结构stack，来支持实现MinStack类的push()、pop()和top()方法。
但是对于min()方法来说，它是用来返回当前堆栈中最小元素的，那么我们可以再创建一个栈结构stackOrder，用来保存一个“不完整”的有序栈，其存储规则如下所示：
- 当新元素
x小于/等于 stackOrder的栈顶元素时，元素x可以保存到stackOrder的栈顶。- 当新元素
x大于 stackOrder的栈顶元素时，元素x不执行入栈操作。
那么通过如上规则，stackOrder中的元素就是从栈顶开始，自上而下逐一变大的，而栈顶就是当前最小的元素。
我们讲完了入栈规则，那么出栈呢？针对于stackOrder来说，出栈规则如下所示：
- 当stack的
栈顶元素等于 stackOrder的栈顶元素时，stack和stackOrder的栈顶元素都出栈。- 当stack的
栈顶元素不等于 stackOrder的栈顶元素时，只有stack的栈顶元素出栈。
好了，基本解题思路描述完毕了，下面我们举例，分别入栈-2、0和-3，然后再执行3次出栈操作，再来看一下stack和stackOrder是如何处理的。具体逻辑如下所示：
3.2> 利用元素记录“入栈那一刻”的最小值
那么除了上面的解题思路外，我们其实也可以创建一个Node节点，里面具有如下3个属性：
- 【int value】当前元素的值；
- 【int min】当前所有入栈元素中，最小的值；
- 【Node pre】前一个入栈元素节点；
那么，针对MinStack类的push()、pop()和top()方法，我们就可以通过构建一个Node链表来实现底层逻辑。而针对min()方法来说，因为每个Node节点都保存了它入栈之前所有入栈元素中，最小的值min，所以直接返回当前节点的min值就可以了。此处就不画图了，具体逻辑可以看下面4.2的源码实现部分。
四、代码实现
4.1> 维护不完整的有序栈
class MinStack {
private Deque<Integer> stack, stackOrder;
public MinStack() {
stack = new ArrayDeque<>();
stackOrder = new ArrayDeque<>();
}
public void push(int x) {
stack.addLast(x);
if (stackOrder.isEmpty() || min() >= x) stackOrder.addLast(x);
}
public void pop() {
int x = stack.removeLast();
if (min() == x) stackOrder.removeLast();
}
public int top() {return stack.getLast();}
public int min() {return stackOrder.getLast();}
}
4.2> 利用元素记录“入栈那一刻”的最小值
class MinStack {
public Node top;
public MinStack() {}
public void push(int x) {
top = new Node(x, top == null ? x : Math.min(x, top.min), top);
}
public void pop() {top = top.pre;}
public int top() {return top.value;}
public int min() {return top.min;}
}
class Node {
public int value, min;
public Node pre;
public Node(int value, int min, Node pre) {
this.value = value;
this.min = min;
this.pre = pre;
}
}
今天的文章内容就这些了：
写作不易，笔者几个小时甚至数天完成的一篇文章，只愿换来您几秒钟的 点赞 & 分享 。
更多技术干货，欢迎大家关注公众号“爪哇缪斯” ~ \(o)/ ~ 「干货分享，每天更新」
