Monotonic Deque: Window Max in O(n)

A deque is a double-ended queue — you can add or remove at both ends in O(1). This animation slides a k-wide frame over an array while a tray of cards below maintains the window's candidates in decreasing order. Each new element enters as a card at the back, first bulldozing every smaller card off the tray (they shatter — a smaller, older element can never again be any window's maximum). Cards whose index has slipped out of the frame pop off the front with an "out of window" tag. The front card always glows: it is the current window's maximum, and each step it stamps its value into a results strip.

What to watch for:

• The tray stays sorted without ever sorting. Decreasing order is maintained purely by evicting on entry.
• Every element gets on and off the tray at most once — total work is O(n), even though some single steps shatter several cards.
• Cards carry indices, not just values. Expiry ("has this card left the window?") is only checkable by index — the detail that breaks value-only implementations.