Daily bit(e) of C++ | MaxStack data structure
Daily bit(e) of C++ #65, Common interview problem: MaxStack data structure
Implement a Max-Stack data structure that provides the following interface:
O(1) complexity methods: top() and max()
O(logn) complexity methods: push(), pop() and pop_max()
Before you continue reading the solution, I encourage you to try to solve it yourself. Here is a Compiler Explorer link with a couple of test cases: https://compiler-explorer.com/z/4bd3qGxd3.
Solution
There are several ways we could approach this problem. I picked a straightforward, albeit wasteful, solution.
The requirements are already pointing us towards ordered containers due to the O(logn) complexity for pop(), pop_max() and push().
For simplicity, we can keep our data twice, once sorted in the LIFO order and once ordered by value. When we pop() or pop_max(), we remove the element from both containers, and symmetrically, when we push(), we insert the element into both containers. The top() and max() are then O(1) queries into the corresponding containers.
Finally, to keep the elements sorted in LIFO order, we need to keep track of an ID that we will assign to every element.
