数据结构: 最小栈

最小栈的特色是保持栈后进先出的特性，同时能够以O(1)复杂度获得当前栈的最小值。

栈是比较好实现的，直接搞个链表，从头部删除和添加即可。

最小栈的核心逻辑是：

因为栈是后进先出的，因此栈顶元素之下的数字永远在栈顶元素之后弹出。

那么当前栈中的最小值, 在栈插入每个元素的过程中，对比一次即可确定下来。

但是在某个元素弹出后，栈中最小值有可能就变了。其最小值的变化和栈顶元素的变化是同步的。因此，可以引入一个辅助栈，

性质1： 辅助栈中的每个元素存储对应主栈中某个元素作为栈顶时的最小值。

操作

push

栈中添加元素时，对比辅助栈栈顶和当前插入元素的大小，确定最小值压入辅助栈。

pop

弹出元素时，因为辅助栈栈顶也应一并弹出，为了维持性质1

top

略

getMin

直接获取辅助栈栈顶元素

Code

class MinStack {public Stack<Integer> aux;public Stack<Integer> main;public MinStack() {aux = new Stack<>();main = new Stack<>();aux.push(Integer.MAX_VALUE);}public void push(int val) {main.push(val);if (val < aux.peek()){aux.push(val);}else{aux.push(aux.peek());}}public void pop() {main.pop();aux.pop();}public int top() {return main.peek();}public int getMin() {return aux.peek();}
}

Reference List

1. https://leetcode.cn/problems/min-stack/solution/zui-xiao-zhan-by-leetcode-solution/