Create a stack which supports
minimum() in O(1)
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.
is to have each stack node keep minimum of all nodes below it.
during each insertion, minimum of new node is just the minimum of
stack top and new node.
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)
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 higher-valued nodes.
When deleting from the stack, new stack-top is compared with the min-stack's top.
If its larger than the min-stack's top, then the top of min-stack is also removed.