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

push(1)pop()   // return 1push(2)push(3)min()   // return 2push(1)min()   // return 1

Note

min operation will never be called if there is no number in the stack.

 

思路是新建一个堆栈用来存储最小值min，每次往stack里push值的时候，如果push的值比min里保存的值小，就把新的值同时push进min里。

在pop的时候要考虑，如果要pop的值刚好是最小值，就要同时把min里的最小值pop掉。

 

java里stack的值保存不同类型，直接用==来判断会出错，需要用equals来判断是否相同。

 

 

public class MinStack {        Stack
       
         stk=new Stack
        
         ();    Stack
         
           min=new Stack
          
           ();    public MinStack() {        // do initialize if necessary            }    public void push(int number) {        // write your code here        if(min.empty()||number<=min.peek())        {            min.push(number);        }        stk.push(number);    }    public int pop() {        // write your code here        if(stk.peek().equals(min.peek()))        {            min.pop();        }                return stk.pop();    }        public int min() {        // write your code here        return min.peek();    }}