Sliding Window Maximum
A monotonic deque of indices keeps the window maximum at the front in amortized O(1).
Sliding Window Maximum: Maximum of every 3
3 enters. The back of the deque is 1, which is not larger than 3 and will leave the window sooner. It can never be the maximum again, so pop it.
Cost
- Best
- O(n)
- Average
- O(n)
- Worst
- O(n)
- Space
- O(k)
Before this
Related
Taught by the same lesson
Sliding Window Maximum covers these too, in the same run.