Implement a stack with min() function, which will return the smallest number in the stack.
It should support push, pop and min operation all in O(1) cost.
Notice
min operation will never be called if there is no number in the stack.
Have you met this question in a real interview?
Yes
Example
push(1)
pop() // return 1
push(2)
push(3)
min() // return 2
push(1)
min() // return 1
class MinStack {
public:
MinStack\(\) {
// do initialization if necessary
}
void push\(int number\) {
// write your code here
m\_stack.push\(number\);
if \(m\_nodeStack.empty\(\)\) {
m\_nodeStack.push\(MinNode\(number, 1\)\);
return;
}
int curMin = m\_nodeStack.top\(\).val;
if \(number < curMin\) {
m\_nodeStack.push\(MinNode\(number, 1\)\);
} else if \(curMin == number\) {
++m\_nodeStack.top\(\).num;
}
}
int pop\(\) {
// write your code here
int top = m\_stack.top\(\);
m\_stack.pop\(\);
if \(top == m\_nodeStack.top\(\).val\) {
--m\_nodeStack.top\(\).num;
if \(m\_nodeStack.top\(\).num == 0\) {
m\_nodeStack.pop\(\);
}
}
return top;
}
int min\(\) {
// write your code here
return m\_nodeStack.top\(\).val;
}
private:
stack<int> m\_stack;
struct MinNode {
MinNode\(int \_val, int \_num\) :
val\(\_val\), num\(\_num\) {}
int val;
int num;
};
stack<MinNode> m\_nodeStack;
};