Expand description
Keep track of the minimum or maximum value in a sliding window.
moving min max provides one data structure for keeping track of the
minimum value and one for keeping track of the maximum value in a sliding
window.
Each element is stored with the current min/max. One stack to push and another one for pop. If pop stack is empty, push to this stack all elements popped from first stack while updating their current min/max. Now pop from the second stack (MovingMin/Max struct works as a queue). To find the minimum element of the queue, look at the smallest/largest two elements of the individual stacks, then take the minimum of those two values.
The complexity of the operations are
- O(1) for getting the minimum/maximum
- O(1) for push
- amortized O(1) for pop