Min Stack

Description

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

Link

Lintcode_ladder

Method

1. use the second stack to store the current minimum value for every push and pop,
   we can o(1) get minimum value in the term of operate the second stack
2. x

Example

1. 1

// use the second stack to store the current minimum value 
// for every push and pop, we can o(1) get minimum value 
// in the term of operate the second stack
class MinStack {
public:
    MinStack() {
        // do initialization if necessary
    }
    // keep minstk.top() is the min value for current depth
    void push(int number) {
        // write your code here
        int tmp;
        // if minstk isEmpty, number is the min 
        if (minstk.empty()) {
            tmp = number;
        } else {
        // otherwise, we compare nubmer and top()
            tmp = std::min(number, minstk.top());
        }
        stk.push(number);
        minstk.push(tmp);
        return;
    }
    int pop() {
        // write your code here
        if (stk.empty() || minstk.empty()) {
            return 0;
        }
        int cur = stk.top();
        stk.pop();
        minstk.pop();
        return cur;
    }
    int min() {
        // write your code here
        if (!stk.empty() && !minstk.empty()) {
            return minstk.top();
        } else {
            return INT_MAX;
        }
    }
private:
    stack<int> stk;
    stack<int> minstk;
};

Similar problems

x

Tags

x