Min Stack
Design a stack that supports push, pop, top, and retrieving the minimum element in constant time.
Constraints:
- Methods pop, top and getMin operations will always be called on non-empty stacks.
Examples:
Input: MinStack minStack = new MinStack(); minStack.push(-2); minStack.push(0); minStack.push(-3); minStack.getMin(); minStack.pop(); minStack.top(); minStack.getMin();
Output: -2
Explanation: The stack is initially empty. We push -2, 0, and -3. The minimum element is -3. After popping, the top element is 0 and the minimum element is -2.
Solutions
Two Stacks
We use two stacks, one for the actual stack and another for keeping track of the minimum elements. When we push an element, we also push it to the minStack if it's smaller or equal to the current minimum. When we pop an element, we also pop it from the minStack if it's equal to the current minimum.
class MinStack {
public: stack<int> stack;
stack<int> minStack;
void push(int x) {
stack.push(x);
if (minStack.empty() || x <= minStack.top()) {
minStack.push(x);
}
void pop() {
if (!stack.empty()) {
if (stack.top() == minStack.top()) {
minStack.pop();
}
stack.pop();
}
}
int top() {
return stack.top();
}
int getMin() {
return minStack.top();
}
}Follow-up:
How would you implement a max stack?
