easy way to create a Max stack in cpp using stl:
(same idea for Min Stack)
stack<pair<int,int>> s;
insert:
int new_max=s.empty()?given_element : max(given_element,s.top().second);
s.push({given_element,new_max});
pop:
if (!s.smpty()){
int popped=s.top().first;
s.pop();
}
else{
}
max:
int maximum_elem=s.top().second;
.
.
and since all operations of stack are O(1) and .first and .second of pair is also O(1)
every operation above of Max Stack is O(1)
and we are storing just pairs of numbers so ofcourse it's O(1) space.