|
Be the first user to complete this post
|
Add to List |
117. Stack with Max Tracking: Find the Largest Element (Optimized)
Objective: In a Stack, keep track of its maximum value. It might be the top element in the stack but once it is popped out, the maximum value should be from the rest of the elements in the stack.
Approach:
- Create another Stack(call it track) to keep track of the maximum in the given Stack(call it main).
- When you insert an element in the main stack for the first time (which means it is empty), insert it in the track Stack as well.
- Now onwards when you insert a new element(say it is x) in the main Stack, peek() the element from the track Stack ( say it is 'a'). Compare x and a and insert it into track Stack whichever is greater.
- When you pop the element from the main stack, pop from the track Stack as well
- So to get to know the maximum element in the main Stack, peek at the element in the track Stack. . See the Example below.
Output:
Max Element is 18 Removing Element 18 Max Element is 14