包含min函数的栈

题目描述

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

 

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

c++代码如下：

class Solution {
public:
     
    stack<int> 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();
    }
     
};