Description

Difficulty: 2.0/5.0

URL: https://oj.leetcode.com/problems/min-stack/

Solution

It looks like a non-trivial question, but the solution is trivial. The problem requires the MinStack to support four operations: pop(), top(), push(), and getMin() in constant time. The normal stack supports the first three in constant time, but not the forth one. The easiest way is to maintain a second stack, saving the currently minimum. When we push a new element, we compare it with the current minimum on the top of the auxiliary stack to know new minimum and push it into the auxiliary stack. When we pop an element, we also pop the auxiliary stack.

A minor improvement is to only record the minimum when the minimum changes and the position where the minimum changes. Though the Big-Oh space complexity is still $O(N)$, but on average we use much less space in reality.

class MinStack {
public:
    MinStack(){
        stk.push(INT_MAX);
        cur_min.push(INT_MAX);
        idx.push(1);
    }
    void push(int x) {
        stk.push(x);
        if (cur_min.top() > x){
            cur_min.push(x);
            idx.push(stk.size());
        }
        
    }

    void pop() {
        if (stk.size() == 1)
            throw runtime_error("Empty MinStack");
        if (stk.size() == idx.top()){
            idx.pop();
            cur_min.pop();
        }
        stk.pop();
    }

    int top() {
        if (stk.size() == 1)
            throw runtime_error("Empty MinStack");        
        return stk.top();
    }

    int getMin() {
        if (stk.size() == 1)
            throw runtime_error("Empty MinStack");
        return cur_min.top();
    }
private:
    stack<int>stk;
    stack<int>cur_min;
    stack<int>idx;
    
};