题目描述
定义栈的数据结构，请在该类型中实现一个能够得到栈中所含最小元素的min函数（时间复杂度应为O（1））。

思路：利用两个栈来进行操作，一个存正常的栈数据，另一个辅助栈存放当前最小值。

  • 入栈时：如果当前没有最小值或者加入的数字小于等于当前的最小值则更新辅助栈，即push新数据，否则不操作，这里注意定义为小于等于就加入，而不是小于，因为比如出现两个相等最小，靠后那个数字被pop掉了此时最小还是那个数，所以辅助栈中维护的应该是一个单调不减的序列。
  • 出栈时：如果当前数据栈栈顶的元素等于辅助栈栈顶的元素，说明这个元素为当前最小，所以pop掉，否则不操作。

Code：

class Solution {
public:
    stack<int> stk1, stk2;
    Solution() {
        while (!stk1.empty()) stk1.pop();
        while (!stk2.empty()) stk2.pop();
    }
    void push(int value) {
        stk1.push(value);
        if (stk2.empty() || stk2.top() >= stk1.top())
            stk2.push(value);
    }
    void pop() {
        if (stk1.top() == stk2.top())
            stk2.pop();
        stk1.pop();
    }
    int top() {
        return stk1.top();
    }
    int min() {
        return stk2.empty() ? -1 : stk2.top();
    }
};