Solution: Max Stack
Let's solve the Max Stack problem using the Custom Data Structures pattern.
We'll cover the following
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:
x
A maximum of
calls can be made to Push( ), Pop( ), Top( ), peekMax( ) and popMax( ). The Pop( ), Top( ), peekMax( ), and popMax( ) methods will always be called on a non-empty stack.
Solution
One straightforward approach is to use two stacks: one to handle the standard stack operations and another to keep track of the maximum values. While this method is intuitive and relatively simple, it can become inefficient when implementing the popMax( ) operation. Finding and removing the maximum element from the stack can take
Level up your interview prep. Join Educative to access 80+ hands-on prep courses.