题目描述

Design a max stack that supports push, pop, top, peekMax and popMax.

push(x) – Push element x onto stack.
pop() – Remove the element on top of the stack and return it.
top() – Get the element on the top.
peekMax() – Retrieve the maximum element in the stack.
popMax() – Retrieve the maximum element in the stack, and remove it. If you find more than one maximum elements, only remove the top-most one.

样例

Example 1:
MaxStack stack = new MaxStack();
stack.push(5); 
stack.push(1);
stack.push(5);
stack.top(); -> 5
stack.popMax(); -> 5
stack.top(); -> 1
stack.peekMax(); -> 5
stack.pop(); -> 1
stack.top(); -> 5

算法1

(list+hashmap) $O(logn)$

用元素存放在doublelinkedlist队首，并将元素的值和iterator放入hashmap中，利用map的logn排序找到最大值

时间复杂度

时间复杂度logn
空间复杂度O（n）

参考文献

C++ 代码

class MaxStack {
public:
    /** initialize your data structure here. */
    MaxStack() {

    }

    void push(int x) {
        l.insert(l.begin(),x);
        m[x].push_back(l.begin());
    }

    int pop() {
        int res=*l.begin();
        m[res].pop_back();
        if(m[res].empty())
            m.erase(res);
        l.erase(l.begin());
        return res;
    }

    int top() {
        return *l.begin();
    }

    int peekMax() {
        return m.rbegin()->first;
    }

    int popMax() {
        int res=m.rbegin()->first;
        auto t=m[res].back();
        l.erase(t);
        m[res].pop_back();
        if(m[res].empty())
            m.erase(res);
        return res;
    }
private:
    list<int> l;
    map<int, vector<list<int>::iterator>> m;
};