C++ O(logN) for write ops, O(1) for reads


  • 0
    E

    We use a doubly linked list for the data, and an ordered map that maps a value to a stack of entries in the list that have that value. To pop an, simply remove the newest element in the list, and pop the corresponding stack in the map. To popMax, pop the stack of entries that is mapped to by the max value, and remove the corresponding entry from the list.

    class MaxStack {
    public:
        list<int> v;
        map<int, vector<list<int>::iterator>> mp;
        
        MaxStack() { 
        }
        
        void push(int x) {
            v.insert(v.begin(),x);
            mp[x].push_back(v.begin());
        }
        
        int pop() {
            int x = *v.begin();
            mp[x].pop_back();
            if (mp[x].empty()) mp.erase(x);
            v.erase(v.begin());
            return x;
        }
        
        int top() {
            return *v.begin();
        }
        
        int peekMax() {
            return mp.rbegin()->first;
        }
        
        int popMax() {
            int x = mp.rbegin()->first;
            auto it = mp[x].back();
            mp[x].pop_back();
            if (mp[x].empty()) mp.erase(x);
            v.erase(it);
            return x;
        }
    };
    

  • 0
    F

    Can someone help translate this to Python? I'm trying but I can't figure out a Python equivalent of map<int, vector<list<int>::iterator>> mp;


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.