题目描述

定义栈的数据结构，请在该类型中实现一个能够得到栈中所含最小元素的min函数（时间复杂度应为O（1））。
注意：保证测试中不会当栈为空的时候，对栈调用pop()或者min()或者top()方法。

思路

需要在时间复杂度为O(1)情况下得到min，想到每次进栈时都进行排序，但是这样就不能保证最后入栈的元素最先出栈。
第二个想法，定义一个最小值存放min，每次进栈时候跟这个min比较并进行更新；但是有个问题，如果这个最小值被取出来了那怎么得到之后的最小值呢，所以我们需要将次最小值也存起来

（看到书上的解法）
定义两个栈，一个主栈，一个辅栈，一个min存放最小值
具体的方法是这样的：
这个辅栈应该和主栈的个数是相同的，他就相当于保存的是主栈这么多个数里的最小值
（1）入栈时，主栈直接进栈，如果value比min小，那么将value进辅栈，并更新min值
（2）出栈时，主栈和辅栈都出栈！但是！！！需要注意，需要更新出完栈操作之后的min，这个min就是辅栈的顶部元素（一定要注意，一开始没考虑到这一点）
（3）top：主栈取顶
（4）min：就是我们定义的min变量，但是需要注意变量名不能和函数名相同

代码

class Solution {
public:
    stack<int> data_stack;  //定义一个主栈
    stack<int> min_stack;   //定义一个辅栈(个数)与主栈个数相同
    int result_min;   //定义当前最小值
    void push(int value) {
        if(data_stack.empty())   //初始化,如果主栈为空，则将value直接赋给min，并且将value直接入辅栈
        {
            data_stack.push(value);  //主栈直接入栈
            result_min=value;
            min_stack.push(value);
        }
        else       
        {
            data_stack.push(value);  //主栈直接入栈
            if(value<result_min)  //如果value比最小值小，则更新最小值，并且将value入辅栈
            {
                min_stack.push(value);
                result_min=value;
            }
            else   //如果value比最小值大，则还是把最小值入辅栈
            {
                min_stack.push(result_min);
            }
        }
    }
    void pop() {
        data_stack.pop();   //出栈操作两个栈同时进行
        min_stack.pop();
        //注意：弹出之后需要更新最小值
        result_min=min_stack.top();
    }
    int top() {
        return data_stack.top();   //取主栈最顶上的
    }
    int min() {
        return result_min;  //min就是当前最小值
    }
};