包含min函数的栈

题目描述：

定义栈的数据结构，请在该类型中实现一个能够得到栈中所含最小元素的min函数（时间复杂度应为O（1））。

解题思路：

1. 由于需要在栈的基础之上再增加一个附加的功能，即返回整个栈中的最小值min，所以我们首先考虑增加一个变量来存储这个最小值min。
2. 但是，稍作思考可以发现的是，当栈中的最小值被弹出之后，我们就无法知道栈中的次小值是什么了。那么，如果再增加一个变量存储此小值呢？
3. 如果这样的话，那么再次小值应该怎么处理呢?
4. 经过上述的思考，我们发现，既然需要额外的空间，我们就再增加一个辅助栈，这个辅助栈的大小与存放数据的栈一样，但是保存栈中存储的最小值
5. 具体做法如下：
   • 数据栈的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;
}