Sliding Window Maximum with Deque
Keep window extremes in O(n).
The Sliding Window Max
Given an array and a window size k, you want the maximum of every window as it slides right. Doing it naively is O(n times k).
A Faster Promise
With a monotonic deque you can answer every window in total O(n) time, scanning the array just once.
All lessons in this course
- Stacks for Matching Brackets
- Monotonic Stack: Next Greater Element
- Queues and collections.deque
- Sliding Window Maximum with Deque