When a recurrence depends on the extremum of previous DP states within a bounded window $[i - K, i - 1]$, maintaining elements in a strictly monotonic deque allows querying the window extremum in $O(1)$ amortized time.
1. Monotonic Queue Invariants
- Front Element: Always holds the optimal DP value for the current window.
- Monotonic Ordering: Elements in the deque are maintained in strictly decreasing (or increasing) value order.
- Out-of-Window Eviction: Elements whose indices fall below $i - K$ are popped from the front.