data structures - Find the maximum and a minimum in a stack -

data structures - Find the maximum and a minimum in a stack -

suppose there 50000+ integer entries in stack? how efficiently find out maximum or minimum in it? stack can grow or cut down i.e., pop() , push(), need maintain track of max , min value in stack?

as mischel pointed out, stack find-min/find-max more efficient o(n)?, answers question.

however response suggests need store each , every max , min @ each point in stack. improve solution have separate stack max , min. max stack force new element onto max stack if new element greater current max, , vice-versa min. pop elements of min , max stacks when element popping of main stack equal them , not equal next element in main stack.

note requires o(n) space while providing o(1) operations.

data-structures stack