题目描述
定义栈的数据结构,请在该类型中实现一个能够得到栈中所含最小元素的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_; };