Monotonic Queue
Learn Monotonic Queue (Queue / Deque, Data Structures & Algorithms) with worked examples, diagrams and interview questions. Free on JavaSchoolLab.
What is a Monotonic Queue? The deque equivalent of a monotonic stack: a deque kept in increasing or decreasing order, but crucially it also needs to evict elements that have SLID OUT of the current window from the FRONT - something a monotonic stack (single-ended) can't do. This is what makes it the tool for sliding-window maximum/minimum problems. Before adding a new element from the back, pop weaker elements from the back (same idea as monotonic stack). Before reading the front (the current max/min), pop anything from the FRONT that has fallen outside the window.