包含min函数的栈
题目描述：
定义栈的数据结构，请在该类型中实现一个能够得到栈中所含最小元素的min函数（时间复杂度应为O（1））。
解题思路：
- 由于需要在栈的基础之上再增加一个附加的功能，即返回整个栈中的最小值min，所以我们首先考虑增加一个变量来存储这个最小值min。
- 但是，稍作思考可以发现的是，当栈中的最小值被弹出之后，我们就无法知道栈中的次小值是什么了。那么，如果再增加一个变量存储此小值呢？
- 如果这样的话，那么再次小值应该怎么处理呢?
- 经过上述的思考，我们发现，既然需要额外的空间，我们就再增加一个辅助栈，这个辅助栈的大小与存放数据的栈一样，但是保存栈中存储的最小值
- 具体做法如下：
- 数据栈的push和pop操作依然与普通栈相同
- 如果，辅助栈的栈中没有存放任何的数据，则将新压入数据栈中的数据压入辅助栈中，作为当前的最小值
- 如果新压入数据栈中的数值小于辅助栈的栈顶值，则将新的数据压入辅助栈，作为当前的最小值
- 如果新压入数据栈中的数值大于辅助栈的栈顶值，则继续将上一轮的最小值压入到辅助栈中
- 这样，每次
push/pop的时候，两个栈同时push/pop，可以保证的复杂度内实现
min()函数
代码
class Solution{
public:
void push(int value) {
data.push(value);
if (min.empty()) {
minValue = value;
min.push(minValue);
}
else {
if (value < minValue) {
minValue = value;
min.push(minValue);
}
else {
min.push(minValue);
}
}
}
void pop() {
if (!data.empty() && !min.empty()) {
data.pop();
min.pop();
}
}
int top() {
if (!data.empty() && !min.empty()) {
return data.top();
}
}
int min() {
if (!data.empty() && !min.empty()) {
return min.top();
}
}
private:
stack<int> data;
stack<int> min;
int minValue;
}
