Min Stack
Desicription
Design a stack that supports push, pop, top, and retrieving the minimum element in constant time.
- push(x) – Push element x onto stack.
- pop() – Removes the element on top of the stack.
- top() – Get the top element.
- getMin() – Retrieve the minimum element in the stack.
Example:
1 2 3 4 5 6 7 8
| MinStack minStack = new MinStack(); minStack.push(-2); minStack.push(0); minStack.push(-3); minStack.getMin(); --> Returns -3. minStack.pop(); minStack.top(); --> Returns 0. minStack.getMin(); --> Returns -2.
|
Solution
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33
|
class MinStack { private: stack<int> numStack; stack<int> minStack; public: void push(int x) { if(minStack.empty() || x <= minStack.top()) minStack.push(x); numStack.push(x); } void pop() { if(numStack.top() == minStack.top()) minStack.pop(); numStack.pop(); } int top() { return numStack.top(); } int getMin() { return minStack.top(); } };
|