Data Structures19 sections · 729 units
Open in Course

Vocabulary - Monotonic Deque

Ordered double-ended

A monotonic deque maintains elements in sorted order, either increasing or decreasing from front to back. For sliding window maximum, use a monotonic decreasing deque.

The front always holds the maximum of the current window. When adding a new element, remove smaller elements from the back. They can never be the maximum while the larger element is in the window.