剑指offer30:包含min函数的栈

题目:定义栈的数据结构,请在该类型中实现一个能够得到栈中所含最小元素的min函数(时间复杂度应为O(1).

思路:对于栈,要在O(1)时间内获得最小元素. 且最小元素要根据进栈出栈动态改变. 当栈为空时,插入一个元素,最小值为此元素. 当插入一个更小的元素时,最小值更新,若此时将新插入的元素出栈,则最小值需要恢复成第一个元素. 因此,最小值元素可用另一个栈来存放,栈顶为当前最小值,存放值的栈每次出栈时对比,若出栈元素为最小值,则将当前最小值从最小值栈弹出.

class Min_stack
{
private:
    stack<int> values;
    stack<int> min_val;
public:
    void push(int value) {
        if(min_val.empty())
            min_val.push(value);
        else{
            int top_min = min_val.top();
            if(value<=top_min)
                min_val.push(value);
        }
        values.push(value);
    }
    void pop() {
        int top = values.top();
        int top_min = min_val.top();
        if(top==top_min)
            min_val.pop();
        values.pop();
    }
    int top() {
        return values.top();
    }
    int min() {
        return min_val.top();
    }
};