Why Monotonic Deque Works

Deque maintains decreasing values (by index).

Invariant: If $i < j$ and $nums[i] < nums[j]$, $i$ can never be max while $j$ exists. Remove $i$.

Front: Current window's max index.

Example: $[1,3,-1,-3,5]$, $k=3$

• $i=0$: $empty$, push : $[0]$
• $i=1$: $3>1$, pop, push: $[1]$
• $i=2$: push: $[1,2]$. Max=$3$
• $i=3$: push: $[1,2,3]$. Max=$3$
• $i=4$: $5>$all, pop all: $[4]$. Max=$5$