NC90 包含min函数的栈

题目描述：

定义栈的数据结构，请在该类型中实现一个能够得到栈中所含最小元素的min函数，并且调用 min 函数、push函数 及 pop函数 的时间复杂度都是 $O\left(1\right)O(1)$O(1)

push(value):将value压入栈中
pop():弹出栈顶元素
top():获取栈顶元素
min():获取栈中最小元素

1. 双栈法

用两个栈模拟1个栈，栈1就是普通的栈，栈2维护最小值，每次入栈1时，判断是不是比栈2顶部的最小值小，如果是，则把该value放入栈2，如果不是，则把栈2的栈顶抄一遍，放入栈2.

这样，min函数就等价于栈2的顶部元素。

图示说明：

class Solution {
public:
    stack<int> stk1, stk2;
    void push(int value) {
        stk1.push(value);
        // 兼容第一次入栈
        if (stk2.empty()) {
            stk2.push(value);
        }
        else {
            stk2.push(stk2.top() < value ? stk2.top() :value);
        }
    }
    void pop() {
        stk1.pop();
        stk2.pop();
    }
    int top() {
        return stk1.top();
    }
    int min() {
        return stk2.top();
    }
};

• 时间复杂度：$O\left(1\right)O(1)$O(1)，没有循环
• 空间复杂度：$O\left(n\right)O(n)$O(n). 定义了长度为$nn$n的辅助栈stk2

2. 暴力做法

只用一个stack，但是求最小值的时候遍历整个stack。

class Solution {
public:
    stack<int> stk;
    void push(int value) {
        stk.push(value);
    }
    void pop() {
        stk.pop();
    }
    int top() {
        return stk.top();
    }
    int min() {
    	// stl的stack不支持遍历，复制一份直接弹出一遍
        stack<int> stk2 = stk;
        int m = INT_MAX;
        while(!stk2.empty()) {
            if (stk2.top() < m) m = stk2.top();
            stk2.pop();
        }
        return m;
    }
};

• 时间复杂度：min函数是$O\left(n\right)O(n)$O(n),其余是 $O\left(1\right)O(1)$O(1)，
• 空间复杂度：$O\left(n\right)O(n)$O(n). 定义了长度为$nn$n的辅助栈stk2