C++ two solutions using 1 stack and 2 stacks with analysis. One/two line(s) for each function.


  • 0

    Using 1 stack: use it to record both value and current min value. This version is fast but consumes some unnecessary space for storing min values:

    class MinStack {
    private:
        stack<pair<int, int>> st;
        
    public:
        /** initialize your data structure here. */
        MinStack() {
            st.push({INT_MAX, INT_MAX});
        }
        
        void push(int x) {
            st.push({x, min(x, st.top().second)});
        }
        
        void pop() {
            st.pop();
        }
        
        int top() {
            return st.top().first;
        }
        
        int getMin() {
            return st.top().second;
        }
    };
    

    Using 2 stacks: one stack for recording values, the other stack for recording min values. This saves more space compared to one stack version, but consumes more run time since it's doing more push/pop as well as extra comparisons:

    class MinStack {
    private:
        stack<int> st, minst;
        
    public:
        /** initialize your data structure here. */
        MinStack() {
            minst.push(INT_MAX);
        }
        
        void push(int x) {
            if (x <= minst.top()) { minst.push(x); }
            st.push(x);
        }
        
        void pop() {
            if (st.top() == minst.top()) { minst.pop(); }
            st.pop();
        }
        
        int top() {
            return st.top();
        }
        
        int getMin() {
            return minst.top();
        }
    };
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.