Design a stack that supports push, pop, top, and retrieving the minimum element in constant time.
push(x) -- Push element x onto stack.
pop() -- Removes the element on top of the stack.
top() -- Get the top element.
getMin() -- Retrieve the minimum element in the stack.
实现一个栈，能返回当前栈里面最小的数。
还记得和这道题类似的是在去年16年喜马拉雅面试的时候遇到的，不过当时是要求用两个栈实现一个栈，能查询到栈里面的最大的一个数，不过道理是类似的。还记得当时第一次遇到这个题，想了好一会儿还是当场做出来了。想想还是有点小激动呢。如果当时选择了喜马拉雅那边的offer可能又是另外一种样子了吧。
思路是用两个栈，一个存压栈的数，一个存最小(如果求最大就存最大）的数。出栈的时候判断是否是最小的那个，如果是那最小的那么将最小的栈也出栈。
public class MinStack {
Stack<Integer> stack = new Stack<>();
Stack<Integer> minSack = new Stack<>();
int min = 0;
/** initialize your data structure here. */
public MinStack() {
}
public void push(int x) {
stack.push(x);
if(minSack.isEmpty()){
minSack.push(x);
min = x;
}else if( x <= min){
minSack.push(min);
min = x;
}
}
public void pop() {
int t = stack.pop();
if(t == min){
min = minSack.pop();
}
}
public int top() {
return stack.peek();
}
public int getMin() {
return min;
}
}
看了下讨论区，也有大神是用一个栈实现的。思路是栈里面压和当前最小数的差值，出栈的时候还原回去就是了。是非常赞的思路。
