Maximum Elements| Stack
TASK (easy)
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.
Function Description
Complete the getMax function in the editor below.
getMax has the following parameters:
- string operations[n]: operations as strings
Returns
int: the answers to each type 3 query
Input Format
The first line of input contains an integer, n. The next a lines each contain an above mentioned query.
Constraints
1 ≤ n ≤ 105
1 ≤ x ≤ 10°
1≤type ≤3
All queries are valid.
Sample Input
STDIN Function
----- --------
10 operations[] size n = 10
1 97 operations = ['1 97', '2', '1 20', ....]
2
1 20
2
1 26
1 20
2
3
1 91
3
Sample Output
26
91
SOLUTION 1
def getMax(operations):
# Write your code here
ansArr = []
stack = []
for s in operations:
t = int(s[0])
if t == 2:
stack.pop()
elif t == 1:
n = int(s[2:])
if stack and stack[-1] > n:
stack.append(stack[-1])
else:
stack.append(n)
else:
ansArr.append(stack[-1])
return ansArr
SOLUTION 2
def getMax(operations, stack=[], mstack=[], output=[]):
for op in operations:
action, *val = op.split()
if action == '1':
stack.append(int(val[0]))
if not mstack or stack[-1] >= mstack[-1]:
mstack.append(stack[-1])
elif action == '2' and stack.pop() == mstack[-1]:
mstack.pop()
elif action == '3':
output.append(mstack[-1])
return output
EXPLANATION STEPS
1. 1 x: Push the integer x onto the stack.
2. 2: Delete the element present at the top of the stack.
3. 3: Print the maximum element in the stack.
