Min Stack

• Time : $O(n)$
• Space : $O(n)$

vector<int> st;
vector<int> mi;
MinStack::MinStack() {
    st.clear();
    mi.clear();
}

void MinStack::push(int x) {
    st.push_back(x);
    if(mi.empty()) mi.push_back(st.size() - 1);
    else {
        if(st[mi.back()] > st.back()) mi.push_back(st.size() - 1);
    }
}

void MinStack::pop() {
    if(st.empty()) return;
    st.pop_back();
    if(st.size() == mi.back()) mi.pop_back();
}

int MinStack::top() {
    if(st.empty()) return -1;
    return st.back();
}

int MinStack::getMin() {
    if(mi.empty()) return -1;
    return st[mi.back()];
}