Create a stack which supports
minimum() in O(1)
If
we keep a variable ‘min’ which will be updated each time
an element from the stack is pushed or popped, it will work only when
element is pushed. During pop, it will be harder to determine the
next minimum if the node being popped was the minimum node.
Solution
is to have each stack node keep minimum of all nodes below it.
So
during each insertion, minimum of new node is just the minimum of
stack top and new node.
During
deletion, minimum of stack is already there in the next top.
Similarly, a max can be kept in each node along with min to give max/min in O(1)
Optimization
If the stack is very large, then the above approach may be wasting a lot of space.
A better approach may be to have a separate stack just to store the minimums.
This stack will store a decreasing order of nodes (from bottom to top) such that a new node will come on top
only when its smaller than the current minimum on this stack
When adding a new node to stack, this approach will store only the decreasing nodes and not the intermediate highervalued nodes.
When deleting from the stack, new stacktop is compared with the minstack's top.
If its larger than the minstack's top, then the top of minstack is also removed.
