两个栈

• 一个栈stkVal用于存储元素，一个辅助栈stkMin，存储压栈过程中的最小值
• push(x)时，若x小于等于stkMin.top()，则x除了正常入栈stkVal外，还需压入stkMin栈
• pop()时，stkVal正常弹出，若stkVal.top()==stkMin.top()时，stkMin也要弹出。

class MinStack {
public:
    stack<int> stackValue;          //正常栈
    stack<int> stackMin;            //辅助单调栈:栈底到栈顶元素单调递减
    MinStack() {

    }
    void push(int x) {          //辅助栈为空，或x<=辅助栈顶元素，则x入辅助栈
        if(stackMin.empty() || x<=stackMin.top())
            stackMin.push(x);
        stackValue.push(x);
    }
    void pop() {                //正常栈和辅助栈栈顶相等时，辅助栈顶才弹出
        if(stackValue.top()==stackMin.top())
            stackMin.pop();
        stackValue.pop();
    }
    int top() {
        return stackValue.top();
    }
    int getMin() {
        return stackMin.top();
    }
};

一个栈

• 每次push(x)时压入两个元素:一个x，一个当前最小元素；
• 每次pop()时连续弹出两个元素

class Minstack{
public:

    stack<int> S;
    MinStack(){}
    void push(int x){
        if(S.empty()){
            S.push(x);
            S.push(x);
        }else{
            int topS=S.top();
            S.push(x);
            if(topS<x){
                S.push(topS);
            }else{
                S.push(x);
            }
        }
    }
    void pop(){
        S.pop();
        S.pop();
    }
    int top(){
        int min=S.top();
        S.pop();
        int topValue=S.top();
        S.push(min);
        return topValue;
    }
    int getMin(){
        return S.top();
    }
};

不用栈，用单链表实现

• 链表尾代表栈底，链表头代表栈顶
• 每个链表结点node除了存储自身值val，还存储以node为栈顶时的最小元素min
• 用链表头插法模拟入栈过程

class MinStack {
public:
    struct stackNode{
        int val;
        int min;
        stackNode *next;

        stackNode(int val,int min):val(val),min(min),next(nullptr){}
    };
    stackNode *head;

    MinStack(){
        head=nullptr;
    }

    void push(int x){
        if(!head)
            head=new stackNode(x,x);
        else{
            auto node=new stackNode(x,min(x,head->min));
            node->next=head;
            head=node;
        }
    }
    void pop(){
        if(head)
            head=head->next;
    }

    int top(){
        if(head)
            return head->val;
        return -1;
    }
    int getMin(){
        if(head)
            return head->min;
        return -1;
    }

};