剑指offer-包含min函数的栈

题目描述

定义栈的数据结构，请在该类型中实现一个能够得到栈中所含最小元素的min函数（时间复杂度应为O（1））。
注意：保证测试中不会当栈为空的时候，对栈调用pop()或者min()或者top()方法。

题解

额外空间复杂度为O(1)，只使用了一个额外变量min_，表示当前最小值。
每次压栈时压入与当前最小值min_（不包括要压栈的元素）的差值，并更新当前最小值min_。
若栈顶元素小于0，说明栈顶元素等于当前最小值min_，出栈时要更新当前最小值为min_ = min_ - stk_.top()
若栈顶元素大于0，则栈顶元素为min_ + stk_.top()，出栈时当前最小值min_不变
代码如下：

class Solution {
public:
    void push(int value) {
        if (stk_.empty()) min_ = value;  // 当栈为空时特殊处理
        stk_.push(value - min_);  // 保存与之前最小值的插值
        if (value < min_) min_ = value;  // 若比之前最小值小，更新最小值
    }
    void pop() {
        if (stk_.top() < 0) min_ = min_ - stk_.top();  // 若比之前的最小值还要小，最小值就是当前值，更新最小值；比之前的最小值大，最小值不变
        stk_.pop();
    }
    int top() {
        if (stk_.top() < 0) return min_;  // 若比之前的最小值还要小，最小值就是当前值
        else return min_ + stk_.top();
    }
    int min() {
        return min_;
    }

private:
    stack<int> stk_;
    int min_;
};