Skip to content

716. Max Stack

  • Time:
    • Constructor: $O(1)$
    • push(x: int): $O(1)$
    • pop(): $O(1)$
    • top(): $O(1)$
    • peekMax(): $O(1)$
    • popMax(): $O(\log n)$
  • Space: $O(|\texttt{push()}|)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
class MaxStack {
 public:
  void push(int x) {
    list.push_front(x);
    keyToIterators[x].push_back(list.begin());
  }

  int pop() {
    const int x = list.front();
    list.pop_front();
    auto& iterators = keyToIterators[x];
    iterators.pop_back();
    if (iterators.empty())
      keyToIterators.erase(x);
    return x;
  }

  int top() {
    return list.front();
  }

  int peekMax() {
    return keyToIterators.begin()->first;
  }

  int popMax() {
    const int x = peekMax();
    auto& iterators = keyToIterators.begin()->second;
    auto it = iterators.back();
    list.erase(it);
    iterators.pop_back();
    if (iterators.empty())
      keyToIterators.erase(keyToIterators.begin());
    return x;
  }

 private:
  std::list<int> list;
  map<int, vector<std::list<int>::iterator>, greater<>> keyToIterators;
};