Solution: Max Stack

Explore how to create a Max Stack data structure that supports standard stack operations and efficient maximum element retrieval. Learn to implement push, pop, top, peekMax, and popMax methods using a combination of stack and max heap along with lazy updates for synchronization.

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 ...