LeetCode: Min Stack

Solution with Stack

Note the requirement of retrieving the minimum element in constant time. For this purpose, we need to use a extra space to store the current minimum element with different top values in in the stack.

#include <stack>
using namespace std;


class MinStack {
    stack<pair<int, int> > s;
public:
    MinStack() { }        

    void push(int x) {
        if(s.empty()) {
            s.push(std::make_pair(x, x));
        } else {
            int n = min(x, getMin());
            s.push(std::make_pair(x, n));
        }
    }

    void pop() {
        s.pop();
    }

    int top() {
        pair<int, int> t = s.top();
        return t.first;
    }

    int getMin() {
        pair<int, int> t = s.top();
        return t.second;
    }
};

Don't miss out!
Subscribe To Newsletter

Want to be better at coding and CS ?

Programming tutorials

Career advice and tips

......

It's Free!

Invalid email address
Last Updated on

Leave a Reply

Your email address will not be published. Required fields are marked *