I have a better implementation for this. Consider storing the elements as the normal stack, but with it we have another stack to store the max element. Whenever we perform push operation on the original stack, we check if it is larger(or equal) than top of currMax stack, if it is we push it into both the stacks, otherwise push it only on the original stack. Now when we perform POP, we check if the top element of original stack is equal to the top element of currMax stack, if it is, then we pop from both the stacks, otherwise pop only from original stack.
Consider the example:
O denotes original stack, M denotes currMax stack. The rightmost element is the top element of the stack
push(5):
O: 5
M: 5
push(6):
O: 5 6
M: 5 6 (since, 6 >= 5)
push(7):
O: 5 6 7
M: 5 6 7 (since 7 >= 6)
pop:
O: 5 6
M: 5 6 (since top of M == element to be popped, i.e. 7 == 7)
max:
returns 6 (top of M)
push(6):
O: 5 6 6
M: 5 6 6 (since 6 >= 6)
push(8)
O: 5 6 6 8
M: 5 6 6 8 (since 8 >= 6)
pop:
O:5 6 6
M: 5 6 6 (since top of M == popped element, i.e 8 == 8)
pop:
O: 5 6
M: 5 6 (again, since top of M == popped element, i.e 6 == 6)
push(5):
O: 5 6 5
M: 5 6 (This time we will not push 5 into M, since 5 >= 6 is false).
So, this requires lesser space and same time complexity. So, the answer according to this is 20 (= 5 * 4)
Am I wrong somewhere?