怎么实现一个最小栈？

实现一个栈，该栈带有出栈（pop）、入栈（push）、取最小元素（getMin）3个方法。要保证这3个方法的时间复杂度都是O（1）。

如果用一个变量 m 保存栈的最小值，我们模拟一下入栈

• 1入栈，此时m 为空，m = 1,
• 2入栈，此时m 为1，2 > 1, m的值不变
• 0入栈, 此时m 为1，0 <= 1, m的值为0

貌似没什么问题，此时从栈顶到栈底依次为 0 2 1，

再模拟一下出栈

• 0出栈，此时m 的值应该更新，但是更新为几呢？ 实际上m的值应该为1，但是我们无从判断。

由此可知，我们只记下最小值还不够，还要记下次小值，次次小值。

方便最小值出栈时，次小值上位成为最小值。

我们可以用另一个栈（B）来保存这些”较小值“，如果此时入栈的元素比栈B的栈顶元素小，及可入栈到栈B，则栈B的栈顶元素就是栈的最小值。

最小栈

#include


class MinStack {
private:
    stack stackA, stackB;
public:
    MinStack() {}
    ~MinStack() {}

    void push(int n) {
        stackA.push(n);
        if (stackB.empty() || n <= stackB.top()) {
            stackB.push(n);
        }
    }

    void pop() {
        if (stackA.top() == stackB.top()) {
            stackB.pop();
        }
        stackA.pop();
    }

    int top() {
        return stackA.top();
    }

    int getMin() {
        return stackB.top();
    }
};