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.
Input Format
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.)
Output Format
For each type 3 query, print the maximum element in the stack on a new line.
Sample Input
10
1 97
2
1 20
2
1 26
1 20
2
3
1 91
3
Sample Output
26
91
Our Approach
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.
|