155. Min Stack (Easy)

Design a stack that supports push, pop, top, and retrieving the minimum element in constant time.

push(x) -- Push element x onto stack. pop() -- Removes the element on top of the stack. top() -- Get the top element. getMin() -- Retrieve the minimum element in the stack. Example:

MinStack minStack = new MinStack();
minStack.push(-2);
minStack.push(0);
minStack.push(-3);
minStack.getMin();   --> Returns -3.
minStack.pop();
minStack.top();      --> Returns 0.
minStack.getMin();   --> Returns -2.

class MinStack {
    stack<int> s;
    stack<int> mins;
public:
    /** initialize your data structure here. */
    MinStack() {

    }

    void push(int x) {
        s.push(x);
        if (mins.empty() || mins.top() >= x) {
            mins.push(x);
        }
    }

    void pop() {
        if (s.top() == mins.top())
            mins.pop();
        s.pop();
    }

    int top() {
        return s.top();
    }

    int getMin() {
        return mins.top();
    }
};

// Solution2: use vector
class MinStack {
    vector<int> s, mins;
public:
    /** initialize your data structure here. */
    MinStack() {

    }

    void push(int x) {
        s.push_back(x);
        if (mins.size() == 0 || mins.back() >= x) {
            mins.push_back(x);
        }
    }

    void pop() {
        if (s.back() == mins.back())
            mins.pop_back();
        s.pop_back();
    }

    int top() {
        return s.back();
    }

    int getMin() {
        return mins.back();
    }
};