题解 | #包含min函数的栈#
包含min函数的栈
http://www.nowcoder.com/practice/4c776177d2c04c2494f2555c9fcc1e49
思路
每次插入删除都维护一个最小值,维护一个保存每一次插入后最小值的栈(辅助栈)
插入时
比较要插入的值和当前最小值,取二者的最小值作为新的最小值,将其插入辅助栈
弹出时
弹出辅助栈栈顶元素,将新的栈顶元素作为更新后的最小值
class Solution { public: stack<int> normal, minval; int min_num = INT_MAX; // 记录当前栈的最小值 void push(int value) { normal.push(value); min_num = std::min(min_num, value); minval.push(min_num); } void pop() { normal.pop(); minval.pop(); min_num = minval.top(); } int top() { return normal.top(); } int min() { return min_num; } };