Introduction to Monotonic Queue Pattern

You are given an array and a window of size K. Report the largest value in every window as it slides along.

[1, 3, -1, -3, 5, 3]   K = 3
windows:  [1, 3, -1] -> 3    [3, -1, -3] -> 3    [-1, -3, 5] -> 5    [-3, 5, 3] -> 5

Scanning each window for its largest value costs O(K) per window, so O(N × K) overall. Neighbouring windows share K - 1 elements, and every one of those is examined again.

Look at the pair 1 and 3. The 3 arrives later and is larger. While 3 is still in the window, 1 can never be the answer