How do you solve Sliding Window Maximum?

Short answer: Monotonic deque storing indices in decreasing height order. As the window slides, pop out-of-window indices from front and smaller values from back. Front is always the max. O(n).

Complexity

Time O(n), Space O(k).

This is a classic “monotonic queue” question — name the pattern.