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.

Notice

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

Example

push(1)

pop() // return 1

push(2)

push(3)

min() // return 2

push(1)

min() // return 1

解题思路：

用一个min stack装同样数量的数字，如果min stack的top比stack新加入的数字小，min stack就不更新数字，保持原有的最小值。

class MinStack {
public:
    /*
    * @param a: An integer
    */
    //MinStack(int a) {
        // do intialization if necessary
    //}

    /*
     * @param number: An integer
     * @return: nothing
     */
    void push(int number) {
        // write your code here
        stackNum.push(number);
        if (minStack.empty()) {
            minStack.push(stackNum.top());
        } else {
            if (minStack.top() <= stackNum.top()) {
                minStack.push(minStack.top());
            } else {
                minStack.push(stackNum.top());
            }
        }
    }

    /*
     * @param a: An integer
     * @return: An integer
     */
    int pop() {
        // write your code here
        int popNum = stackNum.top();
        stackNum.pop();
        minStack.pop();
        return popNum;
    }

    /*
     * @param a: An integer
     * @return: An integer
     */
    int min() {
        // write your code here
        return minStack.top();
    }
private:
    stack<int> stackNum;
    stack<int> minStack;
};