Algorithms and Data Structures · Senior · Question 55 of 75
What does a monotonic deque give you in the "sliding window maximum" problem?
- 1The median of each window in O(1)
- ✓Correct answer: The maximum of each window in O(1), O(n) overall
- 3A sorted copy of every window in O(log n)
Explanation
The deque keeps indices of decreasing values: new values pop smaller ones from the back, and indices that left the window are dropped from the front. Every index enters and leaves once. A median needs two heaps instead.