一、题目描述
设计一个支持 push ，pop ，top 操作，并能在常数时间内检索到最小元素的栈。
实现 MinStack 类:
MinStack()初始化堆栈对象。void push(int val)将元素val推入堆栈。void pop()删除堆栈顶部的元素。int top()获取堆栈顶部的元素。int getMin()获取堆栈中的最小元素。
示例 1:
输入：
["MinStack","push","push","push","getMin","pop","top","getMin"]
[[],[-2],[0],[-3],[],[],[],[]]
输出：
[null,null,null,null,-3,null,0,-2]
解释：
MinStack minStack = new MinStack();
minStack.push(-2);
minStack.push(0);
minStack.push(-3);
minStack.getMin(); --> 返回 -3.
minStack.pop();
minStack.top(); --> 返回 0.
minStack.getMin(); --> 返回 -2.
提示：
-231 <= val <= 231 - 1pop、top和getMin操作总是在 非空栈 上调用push,pop,top, andgetMin最多被调用3 * 104次
二、思路讲解
Java的栈中，push()和pop()的时间复杂度都为o（1），关键在于要寻找最小值，如何实现时间复杂度为o(1)的遍历栈的方法。
其实，我们可以直接维护一个最小值，每次压栈的时候更新即可，关键问题是，当执行出栈操作后，假如将最小值弹出了，那当前最小值是多少呢？那就需要一段空间来保存每个时刻的最小值。
2.1 方法一：辅助栈
这就需要用到辅助栈minStack，该栈的顶部元素即为数据栈中的最小值。当push进一个元素x之后，我们将该元素与minStack栈顶元素比较，若小于栈顶元素，即将栈顶元素进行替换为x。如果数据栈为空，即将x作为最小值。
一句话概况：最小值栈中保存的是每个时刻的最小值。
class MinStack { Stack<Integer> publicStack; //普通栈 Stack<Integer> minStack; //最小值栈 public MinStack() { publicStack = new Stack<>(); minStack = new Stack<>(); } public void push(int val) { publicStack.push(val); //如果压入栈中的不是最小值，那就把minStack中再压入一个最小值 if(!minStack.isEmpty() && val>=minStack.peek()) { minStack.push(minStack.peek()); } else { minStack.push(val); } } public void pop() { publicStack.pop(); minStack.pop(); } public int top() { return publicStack.peek(); } public int getMin() { return minStack.peek(); } } /** * Your MinStack object will be instantiated and called as such: * MinStack obj = new MinStack(); * obj.push(val); * obj.pop(); * int param_3 = obj.top(); * int param_4 = obj.getMin(); */
时间复杂度： O(1)
空间复杂度： O(N)
2.2 方法二：改变压入栈中的元素
是否可以不使用额外空间呢？我们可以将压入栈中的值改为 当前值-当前最小值。以压入栈中值的正负来判断当前值是否是最小值。若是，当前值就是最小值了；若不是，用 (栈中的元素+当前最小值) 即可还原原来的元素。这样只使用了一个栈就记录了每个时刻的最小值，不需要使用额外空间。
详细说一下如何维护最小值：因为每次压入新的元素时，压入的都是与当前栈中最小值的差值（还未压入当前元素），故在弹出元素时，若弹出了当前最小值，因为栈中记录了当前元素与【之前】最小值的差值，故根据这个记录可以更新弹出元素后的最小值。
class MinStack { Stack<Long> stack; long min; public MinStack() { stack = new Stack<>(); } //将当前值与当前最小值的差值压入栈中 public void push(int val) { if(stack.isEmpty()) { stack.push(0L); min = val; } else { //一定要先压栈再更新最小值 stack.push((long)(val - min)); min = Math.min(min, val); } } public void pop() { long pop = stack.pop(); //如果值小于0，说明我们把最小值弹出去了，需要更新最小值 if(pop < 0) { min = min - pop; } } public int top() { //如果栈顶元素小于0，说明栈顶元素就是当前最小值 if(stack.peek() < 0) { return (int)min; } else { return (int)(stack.peek()+min); } } public int getMin() { return (int)min; } } /** * Your MinStack object will be instantiated and called as such: * MinStack obj = new MinStack(); * obj.push(val); * obj.pop(); * int param_3 = obj.top(); * int param_4 = obj.getMin(); */
时间复杂度： O(1)
空间复杂度： O(N)
