Monotonic Queue - How It Works

The deque stores indices in increasing order of their $dp$ values (for finding minimum). When you process position $i$:

$1.$ Remove indices from the front if they're outside the window $[i-k, i-1]$.

$2.$ The front index gives you the minimum $dp$ value in the window.

$3.$ Remove indices from the back while their $dp$ values are $\geq dp[i]$.

$4.$ Add $i$ to the back. Each index enters once and leaves once. Total time: $O(n)$

Time complexity: $O(n)$ amortized for all operations combined.

Space complexity: $O(k)$ for the deque.