Monotonic Queue

A monotonic queue (deque) answers sliding window min/max in O(1) amortized. Maintain indices in decreasing (for max) or increasing (for min) order. Remove from the front when indices fall outside the window, and from the back when the new element is more extreme.