C++ all operations O(1) based on map container


  • 0
    F

    The solution is very simple. We have the list to implement the regular stack - push, we push the incoming number to the head of the list and we store the iterator in the map; pop, we pop the head of the list and erase the number from the map(If there are multiple max, each time we only move one from map, if all gone, then we remove that key). As for max, we can always find the max number in map(last key), as map is sorted by key which is the number in the list. If we need to peek it, return the last key; If we need to popMax, find one iterator pointing to one of the max(could be multiple max), erase it from the list and then erase the iterator from the map.

    class MaxStack {
    public:
    
      MaxStack() {  
      }
    
      void push(int x) {
          l.push_front(x);
          dict[x].push_back(l.begin());
      }
    
      int pop() {
          int ret=*l.begin();
          l.pop_front();
          dict[ret].pop_back();
          if(dict[ret].size()==0) dict.erase(ret);
          return ret;
      }
    
      int top() {
          return l.empty()?-1:*l.begin();
      }
    
      int peekMax() {
          return dict.rbegin()->first;    
      }
    
      int popMax() {
          int ret=dict.rbegin()->first;
          l.erase(*dict[ret].rbegin());
          dict[ret].pop_back();
          if(dict[ret].size()==0) dict.erase(ret);
          return ret;
      }
      private:    
      list<int> l;
      map<int, vector<list<int>::iterator>> dict;
    };
    

    Complexity Analysis

    Time complexity : O(1). All map operations are O(1). And for the c++ list operation, it is still constant.

    Space complexity : O(n). We have all numbers in the list. And we store the numbers and their corresponding iterator in the map.


Log in to reply
 

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