LeetCode 155题解 | 最小栈

一、题目链接

最小栈

二、题目

三、算法原理

栈用数组、链表实现都行，最主要的就是在能在常数时间内检索到最小元素的栈，说明getMin是O(1)的接口。

思路1：用一个变量存储最小元素

用一个变量存储最小元素，push一个值就比较一下并且要判断是否要更新最小元素。但是若更新后再pop一下就会出问题，此时栈中最小元素也会发生改变，那么怎么更新呢？更新成什么数呢？遍历一遍栈吗，这样就是O(n)的接口了，与O(1)不符。

思路2：双栈普通栈和最小栈

采用双栈的方式来实现：普通栈（正常存取数据）和最小栈。

最小栈：若向普通栈中push的元素大于当前最小栈中的栈顶元素，就不用往最小栈中push；若向普通栈中push的元素小于等于当前最小栈中的栈顶元素或者最小栈为空，就向最小栈中push；getMin获取最小栈中的栈顶元素即可。

若再push一个与最小元素相等的元素，那么最小栈中是否也要push呢？—— 要。若没有push，普通栈pop元素-1，此时pop了最小元素，要更新最小值最小栈也pop了，此时最小值理应还是-1而不是1。所以，push的元素比最小栈栈顶元素小或相等，minst都要push这个元素。

当前栈中最小元素是-1，若pop元素7后，最小元素还是-1，此时最小栈不用动。若再pop，此时删除的元素与最小栈中的栈顶元素相等，那么这时最小栈要pop，这时getMin就是1：

不需要写构造、析构、拷贝构造、赋值。类的两个成员变量是自定义类型的，不写构造，编译器自动生成的默认构造会自动调用两个成员变量的默认构造，拷贝构造、析构、赋值同理。

private:
    stack<int> _st;
    stack<int> _minst;

构造函数，像这样啥也不写或直接为空都是可以的：

因为显示写构造了，编译器就不会生成默认构造了。显示写构造，不管有没有写初始化列表，一个类都有初始化列表的。没有显示写初始化列表且没有给缺省值，对于自定义类型的成员会调用它的默认构造。

封装：
封装的简单形态：数据和方法放到类里面，想被看到的封装成公有，不想被看到的封装成私有。
另一层封装的体现：无需关心比如说像这道题的栈的底层是怎么实现的，就只管怎么用即可，知道了功能直接调用对应的功能。

四、编写代码

class MinStack {
public:
    MinStack()
    {}
    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();
    }
private:
    stack<int> _st;
    stack<int> _minst;
};

/**
 * Your MinStack object will be instantiated and called as such:
 * MinStack* obj = new MinStack();
 * obj->push(val);
 * obj->pop();
 * int param_3 = obj->top();
 * int param_4 = obj->getMin();
 */

五、时间复杂度

所有接口的时间复杂度都是O(1)。