考虑状态转移方程： $$ f(i)= \min _ {L(i)\le j \le R(i)} \{g(j)\} + h(i) $$ 其中$i\le N$， $j \le M$。显然暴力的转移复杂度是$O(MN)$。但当$L(i)$和$R(i)$均单调递增，可以将转移的复杂度转移到$O(N)$。维护一个存储$j$的可能取值的单调队列$Q$，并当$i$从小到大变化时，保证：
- 删除（因为$L(i)$的增加）$Q$中小于$L(i)$的元素。
- 在（因为$R(i)$的增加）添加元素之前，删去$Q$中比添加的元素更劣的元素。设当前添加的元素为$j_0$，则$Q$中一个更劣的元素$j_1$需满足$g(j_0) \le g(j_1)$。
- 原因在于由于$j_1$更早被添加，必然满足$j_1<j_0$，那么随着$L(i)$的增加，$j_1$需要比$j_0$更早地被删除，因而在$j_1$能存在在$Q$中的剩余时间里，它永远不能成为被选择的元素。
- （因为$R(i)$的增加）添加元素。
在需要进行状态转移时，取出队列中存在的最早的添加的元素。 考虑队列$Q$的代码实现。设出数组q[M]以及上下界变量l和r。则：
l <= r表示队列中有存在元素。- 初值设为
l=1，r=0，表示队列中不存在元素。 - 对
q[++r]赋值是在队尾添加元素。 - 在队列中存在元素的情况下，
q[l]是取出队首元素，q[r]是取出队尾元素。 - 在队列中存在元素的情况下，
l++表示删除队首元素；r--表示删除队尾元素。
（存疑）更一般地，状态转移方程可以推广为： $$ f(i) = \min _ {j \in S(i)} \{g(j)\} +h(i) $$ 若满足 $$ \forall i_1 < i_2, (\exists i_0 < i_1, j\in S(i_0) ) \land j \not \in S(i_1) \implies j \not \in S(i_2) $$ （这表明当$i$增大时，对符合条件的$j$的集合的每个删除操作都是不需复原的。） 且先添加进队列的元素先被删除，则可以使用单调队列。