Pattern Recognition Drill
Hard Sliding Window
The Problem
Given array nums and window size k, return the max value in each window position.
What approach would you use?
Think about it before scrolling down.
Maintain a decreasing deque of indices. Front is always the max. Remove expired indices. O(n).
Max-heap with lazy deletion of out-of-window elements. O(n log k).
Common Trap
Don't use a simple max() per window — that's O(nk). The monotonic deque gives O(n) total.