Monotonic Queue Optimization
You'll learn how to use a deque (double-ended queue) to maintain range minimums or maximums in constant amortized time, supercharging sliding-window DP problems.
The Core Idea
Imagine you're tracking the minimum value in a sliding window that moves across an array. The naive approach checks every element in the window each time—costly! Monotonic Queue Optimization keeps a deque of candidates that could be the minimum (or maximum), arranged in increasing (or decreasing) order.
The trick: when a new element arrives, you remove useless elements from the back—any element smaller than the newcomer will never be the minimum again because the newcomer is both larger and will stay valid longer. Then you remove expired elements from the front that have slid out of the window.
Why It Works
Think of it like a line of job applicants sorted by skill. If someone arrives who's more skilled and younger than people ahead of them, those older folks can't possibly get hired—so they leave. When you need the best candidate, you just look at the front of the line.
Each element enters the deque once and leaves once, giving O(1) amortized time per operation instead of O(k) for a window of size k.
In DP Context
Many DP problems require finding min(dp[i-k], dp[i-k+1], ..., dp[i-1]) to compute dp[i]. Instead of scanning k elements every time, maintain a monotonic deque of indices (sorted by their dp values). This transforms O(nk) solutions into O(n).
Key Takeaway: Monotonic queues maintain range extrema in O(1) amortized time by discarding elements that can never be optimal, making sliding-window DP problems dramatically faster.