Mono Deque
Last updated
Was this helpful?
Last updated
Was this helpful?
One typical usage of mono-deque is to find the maximum/minimum value in a sliding window.
If we are looking for the maximum value, we can use a descending monoqueue. Example: .
If we are looking for the maximum values in a sliding window. When a large number goes into window, for all the smaller or equal numbers in front of this number, their eviction from the window won't affect the max value of the sliding window, so they can be discarded. In other words, the mono-deque will only contain the numbers that are greater than the current new number, so it's a desending mono-deque.