Design a max stack that supports push, pop, top, peekMax and popMax.
MaxStack stack = new MaxStack(); stack.push(5); stack.push(1); stack.push(5); stack.top(); -> 5 stack.popMax(); -> 5 stack.top(); -> 1 stack.peekMax(); -> 5 stack.pop(); -> 1 stack.top(); -> 5
Intuition and Algorithm\n
A regular stack already supports the first 3 operations, so we focus on the last two.\n
peekMax, we remember the largest value we\'ve seen on the side. For example if we add
[2, 1, 5, 3, 9], we\'ll remember
[2, 2, 5, 5, 9]. This works seamlessly with
pop operations, and also it\'s easy to compute: it\'s just the maximum of the element we are adding and the previous maximum.
popMax, we know what the current maximum (
peekMax) is. We can pop until we find that maximum, then push the popped elements back on the stack.
Our implementation in Python will showcase extending the
Time Complexity: for the
popMax operation, and for the other operations, where is the number of operations performed.
Space Complexity: , the maximum size of the stack.\n
Using structures like Array or Stack will never let us
popMax quickly. We turn our attention to tree and linked-list structures that have a lower time complexity for removal, with the aim of making
popMax faster than time complexity.
Say we have a double linked list as our "stack". This reduces the problem to finding which node to remove, since we can remove nodes in time.\n
We can use a TreeMap mapping values to a list of nodes to answer this question. TreeMap can find the largest value, insert values, and delete values, all in time.\n
Let\'s store the stack as a double linked list
dll, and store a
value to a
MaxStack.push(x), we add a node to our
dll, and add or update our entry
MaxStack.pop(), we find the value
val = dll.pop(), and remove the node from our
map, deleting the entry if it was the last one.
MaxStack.popMax(), we use the
map to find the relevant node to
unlink, and return it\'s value.
The above operations are more clear given that we have a working
DoubleLinkedList class. The implementation provided uses
tail sentinels to simplify the relevant
A Python implementation was not included for this approach because there is no analog to TreeMap available.\n\n
Time Complexity: for all operations except
peek which is , where is the number of operations performed. Most operations involving
TreeMap are .
Space Complexity: , the size of the data structures used.\n
Analysis written by: @awice.\n