155. Min Stack

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

Implement the MinStack class:

• MinStack() initializes the stack object.
• void push(int val) pushes the element val onto the stack.
• void pop() removes the element on the top of the stack.
• int top() gets the top element of the stack.
• int getMin() retrieves the minimum element in the stack.

class MinStack {
    vector<int> st;
    vector<int> mi;
public:
    MinStack() {}
    
    void push(int val) {
        if(st.empty() or st[mi.back()] > val) {
            mi.push_back(st.size());
        }
        st.push_back(val);
    }
    
    void pop() {
        st.pop_back();
        if(mi.back() == st.size())
            mi.pop_back();
    }
    
    int top() {
        return st.back();
    }
    
    int getMin() {
        return st[mi.back()];
    }
};

/**
 * Your MinStack object will be instantiated and called as such:
 * MinStack* obj = new MinStack();
 * obj->push(val);
 * obj->pop();
 * int param_3 = obj->top();
 * int param_4 = obj->getMin();
 */