剑指offer之面试题21:包含min函数的栈
题目:
定义栈的数据结构,请在该类型中实现一个能够得到栈最小元素的min函数。
思路一:
通过每次在压入栈顶的元素与当前最小元素相比后,保存一遍最小元素,每次弹出,都弹出两个,这个就能得到栈当前最小元素了
代码:
class Solution { public: void push(int value) { if(s1.size()==0) { s1.push(value); int min=value; s1.push(min); } else { int min=s1.top(); if(value<min) { min=value; } s1.push(value); s1.push(min); } } //弹出两次 void pop() { int min=s1.top(); s1.pop(); int val=s1.top(); s1.pop(); } int top(){ int min=s1.top(); s1.pop(); int val=s1.top(); s1.push(min); return val; } int min() { return s1.top(); } private: stack<int> s1; };
思路二:利用两个栈,一个栈用于压入数据,另一个栈用于压入数据时的最小元素。无论最小元素是不是压栈的元素,都保存到第二个栈中
代码:
class Solution { public: void push(int value) { if(s1.size()==0) { s1.push(value); s2.push(value); } else { s1.push(value); int min=s2.top(); if(min>value) { s2.push(value); } else { s2.push(min); } } } void pop() { if(!s1.empty()) { s1.pop(); s2.pop(); } } int top() { return s1.top(); } int min() { return s2.top(); } private: stack<int> s1,s2; };