Design MinStack
Design a stack that supports push, pop, top, and getMin operations. The getMin operation returns the minimum element in the stack. Implement the MinStack class.
Constraints:
- Methods pop, top and getMin operations will always be called on non-empty stacks.
- 1 <= x <= 2^31 - 1
Examples:
Input: ["MinStack","push","push","push","getMin","pop","top","getMin"] [[],[-2],[0],[-3],[],[],[],[]]
Output: [null,null,null,null,-3,0,0,-2]
Explanation: MinStack minStack = new MinStack(); minStack.push(-2); minStack.push(0); minStack.push(-3); minStack.getMin(); // return -3 minStack.pop(); minStack.top(); // return 0 minStack.getMin(); // return -2
Solutions
Two Stacks
We use two stacks, one for the actual elements and one for 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:
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();
}
private:
stack<int> stack;
stack<int> minStack;
}
;Follow-up:
How would you implement the MinStack class using a single stack?
