相较普通的栈,题目要求多实现一个操作getMin(): 获取栈中最小的元素
我们维护两个栈:普通栈s保存所有元素, 最小栈min_s保存s中的“曾出现过”的最小元素的递减序列。
min_s.top()即为getMin()的返回值,标识普通栈s里的最小元素。
考虑压栈 3 4 5 2 3 1, 它们有如下表现:
push 3 4 5 2 3 1
s 3 4 5 2 3 1
min_s 3 2 1
亦即,当push(x)的x < min_s.top()时,,我们将x压入min_s中。
大家可以发现,在上述push操作的任意间隔加我们若调用getMin()函数,min_s.top()即为所求。
接下来考虑pop()操作,当且仅当s.top() == min_s.top()时,我们才弹出min_s的元素,这样就可以维护min_s.top()为s里的最小值的性质。
代码:
class MinStack {public:void push(int x){s.push(x);if (min_s.empty() || x<=min_s.top() ){min_s.push(x);}}void pop(){if (min_s.top() == s.top()){s.pop();min_s.pop();} else{s.pop();}}int top(){return s.top();}int getMin(){return min_s.top();}private:stack<int> s;stack<int> min_s;};
真正的爱,应该超越生命的长度心灵的宽度灵魂的深度