Sliding Window Maximum
HardA deque of indices kept in decreasing value order. The front is always the maximum of the current window.
monotonic dequelinear
TimeO(n)
SpaceO(k)
Inputnumbers | window size k
1
0
3
1
-1
2
-3
3
5
4
3
5
6
6
7
7
Window size 3. The deque holds candidate indices, biggest at the front.
1 / 23
for r from 0 to n-1:
while deque and a[deque.back] <= a[r]: pop back
push r
if deque.front <= r - k: pop front
if r >= k-1: output a[deque.front]
Why it matters
Each index is pushed once and popped once, which is why it beats the heap solution.
Keyboard
space play← → stepr restartctrl K search
More in Sliding Window
Next visualiser
Kadane (Maximum Subarray)