Sliding Window — Maximum with a Monotonic Deque

A window of size k slides over nums one position at a time, from the left
edge to the right edge. Return the maximum of each window, in order.

Recomputing each maximum is O(n·k). Keep instead a deque of indices whose
values are strictly decreasing from front to back. The front is always the
current maximum; a new value evicts every smaller value from the back (they
can never be a maximum again), and the front leaves once it slides out of the
window. Each index enters and leaves once: O(n).

Examples

solve([1, 3, -1, -3, 5, 3, 6, 7], 3)  → [3, 3, 5, 5, 6, 7]
solve([1], 1)                         → [1]
solve([9, 8, 7, 6], 2)                → [9, 8, 7]

Constraints

• 1 <= k <= nums.length <= 100000
• The result has nums.length - k + 1 values.