题目：
https://leetcode-cn.com/problems/bao-han-minhan-shu-de-zhan-lcof/
解题思路：
题目要求实现一个包含min()函数的栈，min()函数的作用是返回栈中的最小值，因此我们可以想到使用一个辅助的数据结构来进行实现。
首先我们想到的是一个小根堆或者是一个排序的List，但是题目的要求是时间复杂度为O(1)，这就排除了大多数的解决办法了。
想到时间复杂度为O(1),想必大多数同学都会想到用HashMap,但是再看看案例，再删除一个最小值时还要重新寻找最小值，不可能把Map按从小到大排列吧，因此又排除了Map实现。
但是除了Map的时间复杂度为O(1)，还有其他的数据结构，比如队列、栈。
首先看队列，先进先出，我们不能预知先进的一定是最小的，进而先出的也不一定是最小的，因此排除队列。
接下来只剩栈了，后进先出，我们可以决定后进的一定比先进的小，因此我们就能够实现先出的一定是最小的，所以栈合适！
综上，我们增加一个辅助的栈用来存储最小值，当判断压入的数据小于min栈的栈顶元素时，压入min栈一份，反之不压入，在弹出数据时进行判断min栈和数据栈的栈顶元素是否相等，相等则全部弹出，反之则只弹出数据栈中的元素。
图解：
压入数据:
弹出数据：
代码：
算法：
/** * @desc: 包含min函数的栈 * @author: YanMingXin * @create: 2021/8/26-15:48 **/ public class MinStack { private Stack<Integer> stack; private Stack<Integer> stack1; /** * initialize your data structure here. */ public MinStack() { stack = new Stack<>(); stack1=new Stack<>(); } public void push(int x) { stack.push(x); if (stack1.empty() || stack1.peek() >= x) { stack1.add(x); } } public void pop() { if (stack.pop().equals(stack1.peek())) { stack1.pop(); } } public int top() { return stack.peek(); } public int min() { return stack1.peek(); } }
测试：
public static void main(String[] args) { MinStack minStack = new MinStack(); minStack.push(-2); minStack.push(0); minStack.push(-2); minStack.push(-3); //--> 返回 -3. System.out.println(minStack.min()); minStack.pop(); // --> 返回 0. System.out.println(minStack.top()); //--> 返回 -2. System.out.println(minStack.min()); }
over~
