Max Stack Lintcode

#1

I have solved this question using one other auxiliary stack which takes o(N) as whole time complexity How to do alI operations in following time:-
push: O(logn)
pop: O(logn)
popMax: O(logn)
top: O(1)
peekMax: O(1)

#2

hello @Bhawna

try to think of using dll and map.

refer approach 2 of this article->link

#3

I read but here I didn’t understand how to do ?
Describe me the steps in breif

#4

hello @Bhawna
data structure we are going to use

a) doubly linked list

b) map< int , vector<node *> ,greater< int > > // made it reverse sorted to get max easily
description ->
map[key] will give u vector that contains address of nodes(of dll) whose value is key.

push operation->
simply create new node and add it to the end of ur existing dll.
push its address ( node u created) in end of vector (in the end of this vector map[key])

pop operation ->
simply remove the last node of ur dll
also remove one occurence from map[last node u removed from dll] .
if vector becomes empty after removal then erase key from map

peek max->
simply fetch the first key of map (as it is reverse sorted , the key will give u maximum)

pop max->
do peek max it will give u maximum.
after that simply remove one occurence from map[key u get from peek max]
if vector becomes empty after removal then erase key from map

#5

I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.

On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.