LeetCode:最小栈

155. 最小栈

设计一个支持 push ，pop ，top 操作，并能在常数时间内检索到最小元素的栈。

• push(x) —— 将元素 x 推入栈中。
• pop() —— 删除栈顶的元素。
• top() —— 获取栈顶元素。
• getMin() —— 检索栈中的最小元素。

一、队列实现

思路：栈中每push# 155. 最小栈

设计一个支持 push ，pop ，top 操作，并能在常数时间内检索到最小元素的栈。

• push(x) —— 将元素 x 推入栈中。
• pop() —— 删除栈顶的元素。
• top() —— 获取栈顶元素。
• getMin() —— 检索栈中的最小元素。

一、队列实现

思路：
push：vector存储 栈顶为当前栈顶元素 的最小元素，每次push进栈，vector也随之更新，如果新元素小于vector末尾元素，则vector存入新元素，否则存入原末尾元素。
pop：vector弹出末尾元素，栈弹出栈顶元素
top：返回栈顶元素
getMin：返回vector末尾元素

class MinStack {
public:
    /** initialize your data structure here. */
    stack<int> s;;
    vector<int> v;
    MinStack() {

    }
    
    void push(int x) {
        s.push(x);
        int tmp;
        if(v.empty())  //栈为空时push，此时vecrot也为空
            tmp=x;    
        else
            tmp=v[v.size()-1]<x?v[v.size()-1]:x;  //
        v.push_back(tmp);
    }
    
    void pop() {
        s.pop();
        v.pop_back();
    }
    
    int top() {
        return s.top();
    }
    
    int min() {
        return v[v.size()-1];
    }
};

两个栈实现

思路：栈s1是基础栈。栈s2是辅助栈，存储最小最小值，当push新值时，如果新值小于等于s2栈顶的值，则新值也push到s2。
当pop时，比较s1栈顶值和s2栈顶值是否相等，若相等，说明此时最小值时由s1栈顶值，s1弹出时，s2也要弹出。

class MinStack {
public:
    /** initialize your data structure here. */
    stack<int> s1,s2;
    MinStack() {
  
    }
    
    void push(int x) {
        s1.push(x);
        if(s2.empty())  
        {
            s2.push(x);
        }
        else
        {
            int tmp=s2.top();
            if(x<=tmp)
                s2.push(x);
        }     
    }
    
    void pop() {
        int tmp=s1.top();
        if(tmp==s2.top())  
            s2.pop();
        s1.pop();
    }
    
    int top() {
        return s1.top();
    }
    
    int getMin() {
        return s2.top();
    }
};

一个栈实现

思路：入栈时，比较最小值和当前值，更新最小值，然后当前值入栈，最小值也入栈，这样栈顶是最小值，栈顶下一元素是之前push进的值。
pop时pop两次。top时前弹出并记录栈顶也就是最小值，这时的栈顶是上次压入的值，也就是真的top，然后再把弹出的最小值压入栈中。

class MinStack {
public:
    /** initialize your data structure here. */
    stack<int> s;

    MinStack() {

    }
    
    void push(int x) {
        if(s.empty())
        {
            s.push(x);
            s.push(x);
        }
        else
        {
            int m_min=s.top();
            m_min= x<=m_min?x:m_min;
            s.push(x);
            s.push(m_min);
        }
            
    }
    
    void pop() {
        s.pop();
        s.pop();
    }
    
    int top() {
        int tmp=s.top();
        s.pop();
        int res=s.top();
        s.push(tmp);
        return res;
    }
    
    int getMin() {
        return s.top();
    }
};