Min Stack
Implement a stack with min() function, which will return the smallest number in the stack.
It should support push, pop and min operation all in O(1) cost.
Example
Operations: push(1), pop(), push(2), push(3), min(), push(1), min() Return: 1, 2, 1
Note
min operation will never be called if there is no number in the stack
Solution: 用一个minStack维护最小值，保存每一个状态的最小值。当新来的数比当前的栈顶小的时候，也就是说这个数是最小值，push to minStack，pop的时候要看pop的这个数是不是和minStack的栈顶一样，也就是这个数是最小数，stack.pop()的同时要minStack.pop(). 注意duplicates numbers, 所以push一个和当前最小数一样大的数时，也需要push to minStack.
这里的时间复杂度是平均时间复杂度。
public class Solution {
Stack<Integer> minStack;
Stack<Integer> stack;
public Solution() {
stack = new Stack<>();
minStack = new Stack<>();
}
public void push(int number) {
stack.push(number);
if(minStack.isEmpty()){
minStack.push(number);
}else{
if(minStack.peek()>=number){
minStack.push(number);
}
}
}
public int pop() {
if(stack.peek().equals(minStack.peek())){
minStack.pop();
}
return stack.pop();
}
public int min() {
return minStack.peek();
}
}
