Sliding Window Maximum

Core idea: As a window slides, a smaller value sitting behind a larger, newer one can never be the max again — so throw it away the moment it's beaten. Keep a deque of indices whose values strictly decrease; the front is always the window's maximum, and every element enters and leaves at most once → O(n).

1. The problem, in a fresh setting

You run autoscaling for a service. Every second you record a latency sample. To decide whether to scale, you need the peak latency over the last k seconds, recomputed each second as the window slides forward. Spikes must surface instantly; stale samples must drop out the back.

Given a stream nums and window size k, output the maximum of every length-k window, left to right.

For the first row there are 7 - 3 + 1 = 5 windows; each output is that window's max.