C++ linked list and map O(1) for peek, O(log n) for push and pop


  • 0
    B

    the stack is implemented in linked list so we can remove element in O(1) time when call popMax()

    the node pointers are stored in std::map, since all keys in std::map are sorted so we can always find max element in O(1) time through the rbegin iterator

    push() would be O(log n) since we need to do an insert in std::map

    pop() would be O(log n) since we need to do find and deletion in std::map

    class MaxStack {
    public:
        struct ListNode
        {
            int val;
            ListNode* prev;
            ListNode* next;
            ListNode(int v = 0):val(v), prev(nullptr), next(nullptr){};
        };
        
        ListNode * head;
        ListNode * tail;
        map<int, vector<ListNode*>> address;
        /** initialize your data structure here. */
        MaxStack() {
            head = new ListNode();
            tail = new ListNode();
            head -> next = tail;
            tail -> prev = head;
        }
        
        void push(int x) {
            ListNode * node = new ListNode(x);
            node -> next = head -> next;
            head -> next -> prev = node;
            head -> next = node;
            node -> prev = head;
            address[x].push_back(node);
        }
        
        int pop() {
            ListNode * node = head -> next;
            head -> next = node -> next;
            node -> next -> prev = head;
            address[node->val].pop_back();
            if(address[node->val].empty())
                address.erase(node->val);
            return node->val;
        }
        
        int top() {
            return head -> next -> val;
        }
        
        int peekMax() {
            return address.rbegin()->second.back() -> val;
        }
        
        int popMax() {
            //get node address
            ListNode * node = address.rbegin()->second.back();
            //remove node from stack
            node -> prev -> next = node -> next;
            node -> next -> prev = node -> prev;
            //remove node from address, if vector is empty, remove key
            address[node->val].pop_back();
            if(address[node->val].empty())
                address.erase(node->val);
            return node -> val;
        }
    };
    
    /**
     * Your MaxStack object will be instantiated and called as such:
     * MaxStack obj = new MaxStack();
     * obj.push(x);
     * int param_2 = obj.pop();
     * int param_3 = obj.top();
     * int param_4 = obj.peekMax();
     * int param_5 = obj.popMax();
     */

Log in to reply
 

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