Sliding Window Maximum

Report the maximum of every contiguous block of width k.

Before you code

Decide what the deque remembers: candidate maxima in decreasing value order, oldest first. A new number retires every smaller number behind it, because they can never be the answer while it is around — and numbers that slide out of the window drop off the front.

Hints

1. Store indices, not values, so you can tell when the front entry has left the window.
2. At each step, drop indices at or before i - k from the front, then drop smaller values from the back before appending.
3. Give equal values a consistent rule: removing only strictly smaller values keeps the older equal index, which expires first and keeps the order honest.

Production & complexity notes

When solving Sliding Window Maximum on LeetCode (hard), always state your loop or recursion invariant before writing code. Verify how your chosen data structure behaves on degenerate inputs (single-element inputs, all-duplicate keys, strictly monotonic sequences, or maximum constraint sizes up to $10^5$ elements). In production interviews, pair your implementation with an explicit time and auxiliary space complexity proof, explain why alternative brute-force approaches violate the latency budget, and trace how cache locality and memory allocation overhead affect wall-clock throughput on real hardware. Review the step-by-step memory trace in Deques and monotonic stacks to reinforce the underlying pattern.

What it practices

A monotonic deque that tracks the maximum in linear time, from Deques and monotonic stacks.