Sliding window · 2 of 2
Monotonic queue
Keep a moving window's maximum and minimum with two deques of indices, so the whole scan takes linear time.
Books1
Links2
- Sliding Window Keeps the maximum of a fixed-length window three ways: with a sorted set, a monotonic deque and two stacks. Its With Two Pointers section solves Playlist with a window that holds a set. usaco.guide (opens in a new tab)
- Minimum stack / Minimum queue Three ways to keep a queue’s minimum as elements enter and leave. The third is the two-stack queue. cp-algorithms.com (opens in a new tab)