Sliding Window Maximum

Pattern: Monotonic Queue (Decreasing Deque)

How to Identify This Pattern?

When you see these signs in a problem, think Monotonic Queue:

• Sliding Window of fixed size k.
• Need the Maximum (or Minimum) in every single window position.
• Naive O(n*k) is too slow (Constraints usually N=10^5, K=10^5).

Pattern Intuition: Imagine a line of people ordered by height. When a giant enters the room, everyone shorter than them who came before is now "useless" (they will leave the window sooner AND they are smaller). We maintain a Deque (Double-ended queue) of indices. The Deque is Strictly Decreasing (values).

• Front is always the Max.
• Back is the newest candidate.

Optimal Approach

Why Deque?

• We need O(1) access to strict max (front).
• We need O(1) removal of "useless" small elements from the back (when a larger new element comes).
• We need O(1) removal of "outdated" elements from the front (when they slide out of window).

Algorithm:

1. Initialize Deque dq. Array res.
2. Loop i from 0 to :