Mono Deque
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: 239. Sliding Window Maximum (Hard).
How to memorize?
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.
Problems
Last updated