Solution: Max Stack

Explore the design of a custom Max Stack class that supports push, pop, top, peekMax, and popMax operations. Understand how combining stack and heap data structures enables efficient retrieval and removal of maximum elements. Learn to manage synchronization between these structures with lazy updates to optimize time complexity for interview coding problems.

We'll cover the following...

Statement
Solution
- Time complexity
- Space complexity

Statement

Design a custom stack class, Max Stack, that supports the basic stack operations and can find the maximum element present in the stack.

Implement the following methods for Max Stack:

Constructor: This initializes the Max Stack object.
Void Push(int x): This pushes the provided element, x, onto the stack.
Int Pop( ): This removes and returns the element on the top of the stack.
Int Top( ): This retrieves the most recently added element on the top of the stack without removing it.
Int peekMax( ): This retrieves the maximum element in the stack without removing it.
Int popMax( ): This retrieves the maximum element in the stack and removes it. If there is more than one maximum element, remove the most recently added one (the topmost).

Constraints:

$-1000 \leq$ x $\leq 1000$
A maximum of $100$ calls can be made to Push( ), Pop( ), Top( ), peekMax( ) and popMax( ).
The Pop( ), Top( ), peekMax( ), and popMax( ) methods ...