题目描述
定义栈的数据结构，请在该类型中实现一个能够得到栈中所含最小元素的min函数（时间复杂度应为O（1））。
分析问题：
1、新建一个暂存变量存储最小值，但是当把栈中的最小的元素出栈后，剩下的栈中的最小元素将不知道
2、除了最小元素保存，还要保存次小的元素，以此类推，每一次比较的最小结果都要保存。
为此：
1）新建一个辅助栈保存每次进栈的最小元素
2）出栈时，同时把辅助栈顶返回即是当前栈中的最小元素
class Solution {
public:
void push(int value)
{
//定义一个实际栈StackInt和一个辅助栈StackMin
//实际栈压入栈，每次比较的最小值压入栈
StackInt.push(value);
if(StackMin.empty())
StackMin.push(value);
else if(StackMin.top()<value)
StackMin.push(StackMin.top());
else
StackMin.push(value);
}
void pop() //同时出栈
{
if(!StackInt.empty())
{
StackInt.pop();
StackMin.pop();
}
}
int top() //实际栈的栈顶
{
return StackInt.top();
}
int min() //辅助栈的栈顶
{
return StackMin.top();
}
private:
stack<int> StackInt;
stack<int> StackMin;
};
