155. 最小栈

题目来源：leetcode155. 最小栈 - 力扣（LeetCode）

题目：如下

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

实现 MinStack 类:

• MinStack() 初始化堆栈对象。
• void push(int val) 将元素val推入堆栈。
• void pop() 删除堆栈顶部的元素。
• int top() 获取堆栈顶部的元素。
• int getMin() 获取堆栈中的最小元素。

答案：如下图

class MinStack {
public:

    void push(int val) {
        st.push(val);
        if(minst.empty()||val<=minst.top())
        {
            minst.push(val);
        }
    }
    
    void pop() {
        if(st.top()==minst.top())
        {
            minst.pop();
        } 

        st.pop();
    }
    
    int top() {
        return st.top();
    }
    
    int getMin() {
        return minst.top();
    }

    stack<int> st;
    stack<int> minst;


};

解析：

（1）建立栈

我们可以设计两个栈，一个用于储存所有的值st栈，另一个储存比st栈的第一个进栈的数小于等于的数

stack<int> st;
stack<int> minst;

（2）push接口

使用push接口进栈，st将val全部进栈，开始时，st和minst栈都没有数据，当第一个数进栈st的时候，自然就是最小数，我们就将其拉取进去minst栈中。

min栈中最后一个数作为衡量目前最小数的标准，当比相等或者比其小的时候就入栈

    void push(int val) {
        st.push(val);
        if(minst.empty()||val<=minst.top())
        {
            minst.push(val);
        }
    }

（3）pop接口

先判断，当minst的中的最小值对应st中的top的要被出栈的值的时候就对应的把minst中的最小值出掉

void pop() {
        if(st.top()==minst.top())
        {
            minst.pop();
        } 

        st.pop();
    }

（4）top（）接口

返回当前st栈顶的值

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

}

（5）getMin() 接口

由于minst栈中储存的是按次序排序的最小值，返会其栈顶的值即可

int getMin() {
return minst.top();

}

到这里我们讲解完毕

如果对您有帮助的话点一个免费的赞和收藏叭！

由于作者水平不足，如有任何错误，请读者在评论区交流！