营销策划书范文_食品包装设计的介绍_爱站小工具计算器_中国十大流量网站

定义

队列(Queue)是另一种操作受限的线性表，只允许元素从队列的一端进，另一端出，具有先进先出(FIFO)的特性。但**单调队列(Monotonic Queue)**是一种特殊的队列，它首先是一个双端队列（可在队头/队尾进行读写），其次队列内部的元素单调递增/递减。

单调队列具有以下特性：

• 当前最优解在队头
• 插入元素都是从队尾插入
  • 会剔除队尾不符合单调性的元素(类似栈的出栈动作)
  • 会弹出队头不满足区间限制的元素（单调队列解决的问题一般都带有区间限制）

因此，可以把 单调队列看作是 滑动窗口 和 单调栈 的组合体。

应用场景

• 解决滑动窗口的最值问题
  比如滑动窗口内的最大值问题
  

• 适用于最优化DP(动态规划)算法中动态规划转移，对应的动态转移方程类似 $$f(i)=\underset{l<=j<=r}{\max }(f(j)+b(j)+a(i))=\underset{l<=j<=r}{\max }(f(j)+b(j))+a(i)$$，其中$$\underset{l<=j<=r}{\max }(f(j)+b(j$$