[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 1push(2)push(3)min()   // return 2push(1)min()   // return 1

LeetCode上的原题，请参见我之前的博客.

解法一：

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 -1;        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 -1;    }private:    stack
      
        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
      
        s;};

本文转自博客园Grandyang的博客，原文链接：，如需转载请自行联系原博主。