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

题意整理

实现一个返回最小值的时间复杂度为 $O(1)$ 的栈。正常情况下，栈的push，pop操作都为 $O(1)$ ,但是返回最小值，需要遍历整个栈，时间复杂度为 $O(n)$ 。

思路

最开始看见题的第一反应是用一个中间变量暂存栈内最小值，但细想一下就会发现只用一个中间量暂存最小值的话，在出栈时最小值有可能被弹出从而需要再去找栈内最小值，算法更复杂，因此想到用空间换时间：用另一个栈存储压栈过程中每一次压栈时对应的最小值，主栈出栈时，最小栈同步出栈，min()直接返回最小栈栈顶元素。

具体做法

增加一个最小栈，用空间换时间，在实现时有两种细节有些微差异的方法。

方法一

最小栈只在栈为空或入栈元素小于等于栈顶时压栈，出栈时判断主栈栈顶与最小栈栈顶元素是否相等，相等则同步出栈。

示例：

　　主栈S依次入栈：-1，2，1，-2，4，-3
　　最小栈依次入栈：-1，跳，跳，-2，跳，-3
图解：
图片说明

代码：

class Solution {
private:
    stack<int> S;
    stack<int> Min;
public:
    void push(int value) {
        S.push(value);
        if(Min.empty() || value <= Min.top()){ //如果最小栈为空或栈顶值小于等于value，value入栈最小栈
            Min.push(value);
        }
    }
    void pop() {
        if(Min.top() == S.top()) //若最小栈栈顶元素等于主栈顶元素，最小栈也弹出栈顶
            Min.pop();
        S.pop();
    }
    int top() {
        return S.top();
    }
    int min() {
        return Min.top();
    }
};

复杂度分析

时间复杂度：入栈、出栈以及min都为 $O(1)$
空间复杂度：需要有辅助栈，与输入序列有关，最好为 $O(1)$ ，最差为 $O(n)$

方法二

最小栈如主栈同步压栈，但当压栈元素大于最小栈栈顶时，最小栈压栈自身栈顶元素，出栈时最小栈与主栈同步出栈。

示例：

　　主栈S依次入栈-1，2，1，-2，4，-3
　　最小栈依次入栈：-1，-1，-1，-2，-2，-3
图解：
图片说明

代码：

class Solution {
private:
    stack<int> S;
    stack<int> Min;
public:
    void push(int value) {
        S.push(value);
        if(Min.empty() || value <= Min.top()){ //如果最小栈为空或栈顶值小于等于value，value入栈最小栈
            Min.push(value);
        }
        else
            Min.push(Min.top()); //否则入栈栈顶元素
    }
    void pop() {
        Min.pop();  //最小栈和主栈同步弹出栈顶元素
        S.pop();
    }
    int top() {
        return S.top();
    }
    int min() {
        return Min.top();
    }
};

复杂度分析

时间复杂度：入栈、出栈以及min都为 $O(1)$
空间复杂度：需要有辅助栈，入栈出栈与主栈同步，复杂度为 $O(n)$