题目描述：

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

 

测试用例：

 1）新压入栈的数字比之前的最小值大/小

 2）弹出的数字不是最小的元素/是最小的元素

 

解题思路：

1）借助辅助栈存储最小值，辅助栈顶一定都当前栈的最小值

class Solution {public:    void push(int value) {        if(data.empty()){            data.push(value);            minValue.push(value);  // 是一样的A        }else{ //不为空的时候要寻找最小值，添加到辅助栈中            data.push(value);            if(value
     
      0 && minValue.size()>0);        if(data.empty())            return;        data.pop();//用判断栈为空么？？        minValue.pop();    }    int top() { //访问数据栈顶        return data.top();    }    int min() { //访问辅助栈顶  考虑栈为空的时候        //assert(data.size()>0 && minValue.size()>0);        if(data.empty())            return; //实际上应该报错        return minValue.top();    }    private:    stack
      
        data;    stack
       
         minValue;};
       
      
     

2）使用key-value对存储

class Solution {    typedef pair
     
       pii;    stack
      
        s;public:    void push(int value) {        s.push(pii(value, ::min(value, s.empty() ? value : min()) )); //min()是自己定义的函数s.top().second;    }    void pop() {        s.pop();    }    int top() {        return s.top().first;    }    int min() {        return s.top().second;    }};