题目描述

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

 

思路：用到两个栈：一个栈1全部压，一个栈2压入一个元素后，之后压的元素只能比之前的小于或者等于，这样一来最小的就是在栈2的栈顶，出栈的时候只有当栈1的栈顶元素和栈2的栈顶元素相同时，此时栈2出栈，最小的还是栈2的栈顶元素。

c++代码如下：

class Solution {public:         stack
       
         stack1,stack2;         void push(int value) {        stack1.push(value);        if(stack2.empty())            stack2.push(value);        else if(value<=stack2.top())        {            stack2.push(value);        }    }         void pop() {        if(stack1.top()==stack2.top())            stack2.pop();        stack1.pop();             }         int top() {        return stack1.top();           }         int min() {        return stack2.top();    }     };