[LintCode] Min Stack 最小栈

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

LeetCode上的原题,请参见我之前的博客Min Stack.

解法一:

class MinStack {
public:
MinStack() {} void push(int number) {
m1.push(number);
if (m2.empty() || m2.top() >= number) {
m2.push(number);
}
} int pop() {
if (m1.empty()) return -;
int t = m1.top(); m1.pop();
if (!m2.empty() && m2.top() == t) m2.pop();
return t;
} int min() {
if (!m2.empty()) return m2.top();
return -;
}
private:
stack<int> m1, m2;
};

解法二:

class MinStack {
public:
MinStack():mn(INT_MAX) {} void push(int number) {
if (number <= mn) {
s.push(mn);
mn = number;
}
s.push(number);
} int pop() {
int t = s.top(); s.pop();
if (t == mn) {
mn = s.top(); s.pop();
}
return t;
} int min() {
return mn;
} private:
int mn;
stack<int> s;
};
上一篇:HDU 3103 Shoring Up the Levees(计算几何 搜寻区域)


下一篇:HTTP协议中返回代码302的情况