Stack/QueueStack & Queue

Monotonic Queue (Sliding Window Maximum)

A deque kept in sorted order so the max (or min) of a sliding window is always at the front.

Learn Monotonic Queue →
a
1
0
3
1
-1
2
-3
3
5
4
3
5
6
6
7
7
deque (front → back, idx:val)
window maxima
1/23Maximum of every window of size k=3. A deque keeps candidate indices with decreasing values: the front is always the current maximum, and anything smaller than a newer element can never be a maximum again.
Current windowEntering elementIn dequeWindow maximumEvicted
PseudocodeLearn Monotonic Queue →
1dq = deque()  # indices, values decreasing front→back
2for i in 0 .. n-1:
3  while dq and a[dq.back] <= a[i]: dq.pop_back()
4  dq.push_back(i)
5  if dq.front <= i - k: dq.pop_front()
6  if i >= k-1: out.append(a[dq.front])
Variables
k3
Complexity
access O(1)
search O(k)
insert O(1) amortized
delete O(1)
Speed