Coder's Cat

LeetCode: Min Stack

2020-02-14

LeetCode Challenge Description: 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;
}
};

Preparing for an interview? Check out this!