实现一个栈, 支持以下操作:

• push(val) 将 val 压入栈
• pop() 将栈顶元素弹出, 并返回这个弹出的元素
• min() 返回栈中元素的最小值

要求 O(1) 开销.

样例

样例 2:

输入: 
  push(1)
  min()
  push(2)
  min()
  push(3)
  min()
输出: 
  1
  1
  1

注意事项

保证栈中没有数字时不会调用 min()

 

class MinStack {
    vector<int> mystack;
    int mymin;
    int count;
public:
    
    
    MinStack() {
        // do intialization if necessary
        mymin =   INT_MAX;
        count = 0;
    }

    /*
     * @param number: An integer
     * @return: nothing
     */
    void push(int number) {
        // write your code here
        mymin = (number < mymin) ? number : mymin;
        mystack.push_back(number);
        count++;
    }

    /*
     * @return: An integer
     */
    int pop() {
        // write your code here
        int ret = mystack[count - 1];
        mystack.erase(mystack.begin() + count-1 );
        //cout<<"mystack.size() = "<<mystack.size()<<endl;
        mymin =   INT_MAX;
        vector<int>::iterator iter;
        for (iter=mystack.begin();iter!=mystack.end();iter++)
        {
            //cout<<"*iter = "<<*iter<<endl;
            //cout<<"min = "<<min<<endl;
            mymin = (*iter < mymin) ? *iter : mymin;
        }
        
        
        count--;
        return ret;
    }

    /*
     * @return: An integer
     */
    int min() 
    {
        
        // write your code here
        return mymin;
    }
};