C++：利用map实现整体时间复杂度O(1)

vector实际上就是一个stack的封装类。所以直接用vector的成员函数就可以很容易的实现栈的基础操作。

public:
    vector<int> pool;

    void push(int value) {
        //不能这么写：pool[head] = value; 在最开始，vector没有申请到任何空间，因此pool[head]这个访问操作
        //是非法的。访问操作不会申请额外空间。
        pool.push_back(value);
    }

    void pop() {
        pool.pop_back();
    }

    int top() {
        return pool.back();
    }

重点在这：

请在该类型中实现一个能够得到栈中所含最小元素的min函数（时间复杂度应为O（1））。

最容易想到的方法当然是从头到尾查询整个栈中最小值，但这个方法是O(N)的，显然不可行。
当然你也可以把这个时间成本转移到其他函数：
维护一个int类的mini变量，在每一次对栈有修改，即入栈push或出栈pop操作完成后，从头到尾查询栈中的最小值，用该值更新mini。调用min()函数时直接返回mini的值即可。
题目是过了，但其实也只是在骗自己XD，面试官当然不会对这个答案感到满意。

我给出的解决方案是：使用键值对数组map以空间换时间。
维护一个键和值都为int类型的map容器times,在每次对栈进行修改时，我们在times中进行相应的“记录”。

public：
    vector<int> pool;
    map<int,int> times;//<栈中元素的值，出现次数>

    void push(int value) {
        pool.push_back(value);
        times[value]++;//使times中键为value的值++
    }

    void pop() {
        //将即将出栈的元素作为键，使其对应的值--，并检查该值是否还在栈中存在（出现次数是否为0）
        if(--times[pool.back()] == 0)
        {
            times.erase(pool.back());//已不在栈中存在的值，我们将其对应的键值对从times中移除掉
        }
        pool.pop_back();
    }
    int top() {
        return pool.back();
    }

对于键值对map容器来说,通过下标访问/修改一个键的值，就像我们所熟知的int类数组通过下标访问一个元素一样，时间复杂度是都是O(1)，所以更新栈操作push、pop的时间复杂度也为O(1)。
注意当一个数不再存在在栈中时，我们要将其从times中移除掉，而不是只将他的值改为0。否则最后这招就不好使了：

int min() {
        return times.begin()->first;
    }

map容器中的各个元素是按 键key 进行排序的。对于int类型的键自然是按大小排序了，所以times中的第一个元素times.begin()的键就是我们要找的最小值。用->first访问一个键值对的键，用->second来得到它的值。

这样，整个类中的各个函数我们都实现了时间复杂度为O(1)。