题解 | #包含min函数的栈#

方法一：辅助栈
核心思想：
普通栈的 和 函数的复杂度为，满足题目要求。但获取栈最小值的 函数需要遍历整个栈，复杂度为，所以本题的主要目的就在于优化对栈的最小值的获取，这可以通过使用一个具有单调性的辅助栈来实现。
具体思路：
数据栈：数据栈用于存储所有元素，保证函数的正常逻辑。
辅助栈：辅助栈中存储数据栈中所有降序的元素。栈具有先进后出的特点，所以一个值压入栈中后，只要未被弹出，所有在它之后进行压栈的小于该值的元素都不会成为最小值，可以不压入辅助栈，这可以保证辅助栈栈顶即为数据栈中所有数据中的最小值。

函数说明： 压栈时，只有辅助栈为空，或该数值不大于辅助栈栈顶元素，才对辅助栈进行压栈。 出栈时，如果数据栈栈顶元素与辅助栈栈顶元素相等，说明该数值被弹出，也需要同时对辅助栈进行出栈。
核心代码：

class Solution {
private:
    stack<int> sk;
    stack<int> help;
public:
    void push(int value) {
        sk.push(value);
        //保证辅助栈的单调性
        if(help.empty() || value <= help.top()) {
            help.push(value);
        }
    }
    void pop() {
        //如果辅助栈栈顶值与数据栈栈顶值相等则出栈
        if(help.top() == sk.top()) {
            help.pop();
        }
        sk.pop();
    }
    int top() {
        return sk.top();
    }
    int min() {
        return help.top();//辅助栈栈顶既为最小值
    }
};

复杂度分析：
时间复杂度：，对单个操作，四个函数的时间复杂度均为常数级别
空间复杂度：，最坏情况下，辅助栈也需要存储所有元素，使用空间

方法二：单个栈
核心思想：
也可以使用单个栈完成功能，但此时的栈不是存储数据，而是存储数据与当前最小值的差值，并另外存储一个最小值
函数说明： ：压栈时，当栈为空时，存储最小值，压入差值0。栈不为空时，压入数据与当前最小值的差值，如果差值为负，则更新最小值 :出栈时，如果此时栈顶值为负数，说明此处发生的最小值的变化，需要更新最小值。 :如果栈顶值为负数，说明最小值在此处更新，此时返回最小值即可。如果栈顶值为正数，即为最小值与数据的差值，相加后进行返回 :直接返回存储的最小值即可
核心代码：

class Solution {
private:
    stack<long> sk;//记录与最小值差值，由于可能大于INT_MAX，使用long
    long tmin;//记录最小值
public:
    void push(int value) {
        if(sk.empty()) {
            //当栈为空，最小值即为当前值，差值为0
            sk.push(0);
            tmin = value;
        } else {
            //压入与最小值的差值
            sk.push(value - tmin);
            if(value < tmin) {
                //如果当前值小于最小值，进行更新
                tmin = value;
            }
        }
    }

    void pop() {
        if(sk.top() < 0) {
            //差值为负数，说明当前位置最小值发生改变，需要改回该元素压入前的最小值
            tmin -= sk.top();
        }
        sk.pop();
    }

    int top() {
        if(sk.top() < 0) {
            return tmin;//此时最小值刚进行更新
        } else {
            return tmin + sk.top();
        }
    }
    int min() {
        return tmin;
    }
};

复杂度分析：
时间复杂度：，对单个操作，四个函数的时间复杂度均为常数级别
空间复杂度：,只使用了常数个变量