When to Use Monotonic Queue

Look for these patterns to recognize monotonic queue improvement:

$1.$ DP transition needs min/max over a sliding window: $dp[i] = \min_{j=i-k}^{i-1}(f(j)) + g(i)$.

$2.$ Fixed or bounded window size $k$.

$3.$ You're iterating through positions sequentially.

$4.$ No complex dependencies between the function $f$ and $g$. The improvement works when candidates can be "dominated." If a newer candidate is as good or better than an older one, the older one will never be chosen.