1. One-Liner
Use a deque of indices with decreasing values from front (max) to back; drop out-of-window and smaller useless elements.
2. The Problem It Solves
Needed for streaming max filters, CPU schedulers, and competitive programming window templates.
3. The Core Idea
For each new index, pop back while last value ≤ current (they can’t be max while current lives). Pop front if index left window. Front is window max.
4. How It Works (Step-by-Step)
| Step | Action |
|---|---|
| 1 | Deque stores candidate indices |
| 2 | Before push i, pop back while a[back]≤a[i] |
| 3 | Push i; pop front if front≤i-k |
| 4 | From i≥k-1 record a[front] |
5. Dry Run Example
nums [1,3,-1,-3,5,3,6,7], k=3: window maxes [3,3,5,5,6,7].
6. Key Properties
| Property | Detail |
|---|---|
| Monotonic deque | Amortized O(1) per index |
| Min variant | Flip comparison |
| Multi-pass | Not needed |
7. Where It Is Used
| Domain / System | Use |
|---|---|
| Signal processing | Moving max |
| Finance | Rolling highs |
| Systems | Rate windows |
8. Interview Tips
Contrast with heap O(n log k). For min-cost problems combine with two deques.
9. Comparison with Other Algorithms
| Technique | Notes |
|---|---|
| Heap | O(n log k), harder eviction |
| ST / RMQ | Static arrays different |
| Brute | O(nk) |
10. Complexity
| -- | -- |
|---|---|
| Time | O(n) |
| Space | O(k) deque |
Implementation Example (PYTHON)
from collections import deque
def max_sliding_window(a, k):
dq, out = deque(), []
for i, x in enumerate(a):
while dq and a[dq[-1]] <= x: dq.pop()
dq.append(i)
if dq[0] <= i - k: dq.popleft()
if i >= k - 1: out.append(a[dq[0]])
return out