• 单 调 队 列 的 内 容 单调队列的内容 单调队列的内容

顾名思义, 始终 单调递增 或 单调递减 的 双端队列 即为单调队列 .

接下来以 滑动窗口 为例说一下基础的单调队列操作.

设当前枚举到了 A i A_i Ai​, 且维护的是从队首到队尾单调递增的队列, (队首比队尾入队时间早)

  1. 若队列为空, 直接将 A i A_i Ai​ 入队.
  2. 若队列不为空, 设队尾为 b k bk bk,
    1. 若 A b k &gt; A i A_{bk}&gt;A_i Abk​>Ai​, 则不断弹出队尾, 直到 A b k &lt; = A i A_{bk}&lt;=A_i Abk​<=Ai​.
    2. 若 A b k &lt; = A i A_{bk}&lt;=A_i Abk​<=Ai​, 直接从队尾入队 .

由于 队首 可能不在题目中的 “滑动窗口” 中, 所以每次输出答案时要弹掉不合法的元素, 最后最小值即为 队首 .

时间复杂度 O ( N ) O(N) O(N) .

最大值同理, 这里不再赘述.

  • 单 调 队 列 的 应 用 单调队列的应用 单调队列的应用

单调队列同样可以作为 斜率优化 实现的工具, 没学过斜率优化的同学可以点击 这里.

例题 .