剑指 Offer 30. 包含min函数的栈（c++）——005

剑指 Offer 30. 包含min函数的栈（c++）——005

题目链接

思路：

题目一看，easy!不就定义一个变量，记录最小值输出吗。那pop之后呢？有小丑……
这道题是看了题解写的，先留着，等过几天再来回忆可能会好些吧。

代码：

class MinStack {
public:
    stackassistStack;
    stack myStack;
    
    MinStack() {
        
    }
    
    void push(int x) {
        myStack.push(x);
        if(assistStack.empty()||x<=assistStack.top()){
            assistStack.push(x);
        }
    }
    
    void pop() {
        int mid = myStack.top();
        myStack.pop();
        if(mid==assistStack.top()){
            assistStack.pop();
        }
    }
    
    int top() {
        return myStack.top();
    }
    
    int min() {
        return assistStack.top();
    }
};

未曾想过的方法：

class MinStack
{
public:
    stack st;
    int Min = INT_MAX;
    MinStack()
    {
    }

    void push(int x)
    {
        st.push(Min);
        if (x < Min)
            Min = x;
        st.push(x);
    }

    void pop()
    {
        st.pop();
        Min = st.top();
        st.pop();
    }

    int top()
    {
        return st.top();
    }

    int min()
    {
        return Min;
    }
};

每次push()都为先向栈垫一个数据——添加前栈中的最小值，这样，每次pop()后都可以获取该数据即得到当前栈中最小值。
例如依次执行以下 *** 作：（其中高亮的就是添加前栈中最小值）

push(3)
栈由底到顶：INT_MAX 3
push(2)
栈由底到顶：INT_MAX 3 3 2
push(7)
栈由底到顶：INT_MAX 3 3 2 2 7

push(4)
栈由底到顶：INT_MAX 3 3 2 2 7 2 4

pop()
栈由底到顶：INT_MAX 3 3 2 2 7

push(4)
栈由底到顶：INT_MAX 3 3 2 2 7 2 4

pop()
栈由底到顶：INT_MAX 3 3 2 2 7