Problem Reference: Maximum Element
You have an empty sequence, and you will be given N queries. Each query is one of these three types:
- 1 x -Push the element x into the stack.
- 2 -Delete the element present at the top of the stack.
- 3 -Print the maximum element in the stack.
The first line of input contains an integer, N. The next N lines each contain an above mentioned query. (It is guaranteed that each query is valid.)
For each type 3 query, print the maximum element in the stack on a new line.
Our approach is pretty straight forward. We will use two stacks here.
The first stack is to keeping track of all the elements to perform push and pop (element stack). And the other
is for keeping track of the maximum element (maximum elements stack).
When you read the first element, push it onto both of the stacks.
We maintain the maximum elements stack so that the maximum element till now is on the top. Whenever we push an element, it normally goes to the elements stack,
but we also push it to the maximum elements stack if, and only if, it is greater than the current maximum element.
Now, when an element is to be deleted, we pop it directly from the elements stack. We also check if that particular element is the maximum element or not.
We do so by comparing the value and the index of the popped element with the element on top of the maximum elements stack. If they are equal, we pop that element as well.
Finally, to answer the maximum element query 3, we print the element on top of the maximum elements stack.