更多“顺序栈中数据元素与栈顶指针的变化：非空栈中的栈顶指针top始终在的 （）下一个位置”相关的问题

数据结构中队列有很多，例如：先进先出队列、双端队列、单调队列、优先队列（堆） 等等。我来简单介绍一下吧。

「 数据结构 」 和 「 算法 」 是密不可分的，两者往往是「 相辅相成 」的存在，所以，在学习 「 数据结构 」 的过程中，不免会遇到各种「 算法 」。
数据结构 常用的操作一般为：「 增 」「 删 」「 改 」「 查 」。基本上所有的数据结构都是围绕这几个操作进行展开的。那么这篇文章，作者将用 「 十张动图 」 来阐述一种 「 一端插入 」「 两端删除 」 的数据结构「 单调队列 」 。

单调队列的操作浓缩为以下一张图：

看不懂没有关系，我会把它拆开来一个一个讲。

【例题1】给定一个长度为 整数数组 ，有一个大小为 的滑动窗口从数组的最左侧移动到数组的最右侧。只能看到在滑动窗口内的 个数字。滑动窗口每次只向右移动一位。返回 每个滑动窗口 的最大值。

看到这个问题，最简单的思路就是：枚举一个起点 ，然后记录区间 内的最大值。枚举起点的时间复杂度为 ，记录区间最值的时间复杂度为 ，所以总的时间复杂度为 ，对于这个问题的数据量，最大的数据量达到了 量级，所以这个做法是行不通的。

这个问题是个经典的区间最值问题，可以通过 ST表 (Sparse Table, 稀疏表) 求解，时间复杂度为 ，除了 ST表，还可以采用 线段树 求解区间最值，时间复杂度也为 。当然，这两块内容都不是本文讨论的重点，如果对 ST表 感兴趣，可以参考以下文章：。对线段树感兴趣，可以参考以下文章：。

本文将介绍一种 的算法。它将会用到一种数据结构 —— 单调队列。在这个问题中，两个相邻的滑动窗口，实际上只相差两个元素，如下图所示：

假设，我们提供了一种容器，这个容器能够支持三种操作：
1）【询问】通过 的时间，获取容器中元素的最大值。
2）【删除】通过 的时间，删除元素；
3）【插入】通过 的时间，插入元素；

那么，我们只要不断的移动滑动窗口，每一次移动，删除一个元素，插入另一个元素，并且记录下最大值，那么，每一次滑动，只需要三步 的操作。总共 次滑动，只需要 的时间复杂度就能解决这个问题。 这种容器存在吗？让我们首先简单了解一下 FIFO 队列 和 双端队列，如果你对 以上两种数据结构 已经 了如指掌，则可以跳过相关内容，直接观看

队列 是仅限在 一端 进行 插入，另一端 进行 删除 的 线性表。

允许进行元素删除的一端称为 队首。如下图所示：

允许进行元素插入的一端称为 队尾。如下图所示：

队列的插入操作，叫做 入队。它是将 数据元素 从 队尾 进行插入的过程，如图所示，表示的是 插入 两个数据（绿色 和 蓝色）的过程：

队列的删除操作，叫做 出队。它是将 队首 元素进行删除的过程，如图所示，表示的是 依次 删除 两个数据（红色 和 橙色）的过程：

队列的清空操作，就是一直 出队，直到队列为空的过程，当 队首 和 队尾 重合时，就代表队尾为空了，如图所示：

对于一个队列来说只能获取 队首 数据，一般不支持获取 其它数据。

队列元素个数一般用一个额外变量存储，入队 时加一，出队 时减一。这样获取队列元素的时候就不需要遍历整个队列。通过 的时间复杂度获取队列元素个数。

当队列元素个数为零时，就是一个 空队，空队 不允许 出队 操作。

队列的实现，可以参考以下这篇文章：

双端队列 是一种具有 队列 和 栈 的性质的数据结构，是我们常说的 deque（double-ended queue），是一种限定 插入 和 删除 操作在表的两端进行的线性表。这两端分别被称为 队首 和 队尾。

双端队列的一端被称为 队首，如下图所示：

双端队列的另一端被称为 队尾，如下图所示：

队列的插入操作，叫做 入队。

队首入队 就是将 数据元素 从 队首 进行插入的过程。如图所示，表示的是在队首 插入 一个蓝色数据的过程：

队尾入队 就是将 数据元素 从 队尾 进行插入的过程。如图所示，表示的是在队尾 插入 一个紫色数据的过程：

队列的删除操作，叫做 出队。队首出队 是将 队首 元素进行删除的过程，如图所示，表示的是在队首 删除 一个蓝色数据的过程：

队尾出队 是将 队尾 元素进行删除的过程，如图所示，表示的是在队尾 删除 一个紫色数据的过程：

队列的清空操作，就是一直 出队，直到队列为空的过程，当 队首 和 队尾 正好错开一个位置时，就代表队尾为空了，如图所示，细心的读者会发现，队尾 和 队首 错开了一个位置：

队列元素个数一般用一个额外变量存储，入队 时加一，出队 时减一。这样获取队列元素的时候就不需要遍历整个队列。通过 的时间复杂度获取队列元素个数。

当队列元素个数为零时，就是一个 空队，空队 不允许 出队 操作。

队首指针 指向的数据被称为 队首元素，可以通过 的时间复杂度来获取。

队尾指针 指向的数据被称为 队尾元素，可以通过 的时间复杂度来获取。

需要了解双端队列的实现，可以参考如下文章：

单调队列 就是能够完美支持下面三种操作的一种容器：
1）【询问】通过 的时间，获取容器中元素的最大值。
2）【删除】通过 的时间，删除元素；
3）【插入】通过 的时间，插入元素；

单调队列是一个限制只能 队尾插入，但是可以 两端删除 的 双端队列 。单调队列 存储的元素值，是从 队首 到 队尾 呈单调性的（要么单调递增，要么单调递减）。

对于求解最大值的问题，则需要维护一个 单调递减 的队列。

如图所示，⑨ 为原先的 队首元素，执行 队首删除（出队） 操作以后，⑥ 成为新的 队首元素；而在队尾执行插入④这个元素的时候，为了保持单调性，需要将①②依次从队尾删除；当队尾执行插入②这个元素的时候，满足单调性。

由于单调队列是单调递减的，所以队首元素 最大，直接 获取队首元素。

如图所示，head 指向 队首元素，直接获取，由于这是一个单调递减队列，所以得到的，就是最大值。

删除分为 队首删除 和 队尾删除。 队首删除即直接队首元素出队， 即可完成操作。如图所示：

队尾删除 一般是配合 队尾插入 进行的。我们接着往下看。

在进行 队尾插入 的时候，我们往往需要明白一个重要的点，就是需要保证它 单调递减 的性质，所以如果 队尾元素 插入元素 ，则当前的 队尾元素 是需要执行删除操作的（也就是上文提到的 队尾删除），直到满足 队尾元素 插入元素，才能真正执行 插入 操作。

这样才能保证，执行 队尾插入 后，单调队列仍然是 单调递减 的。插入过程，虽然伴随着元素的删除，但是每个元素至多被 插入一次 和 删除一次，所以均摊时间复杂度还是 $O(1)$ 的。

如图所示，在队尾执行插入④这个元素的时候，为了保持单调性，需要将①②依次从队尾删除；当队尾执行插入②这个元素的时候，满足单调性，所以直接执行插入操作。

由于单调队列执行插入的时候，一定是从队尾进行插入，所以单调队列中的数据，从队首到队尾的顺序，一定是和原序列严格保序的；

为了让单调队列的数据足够干净，在单调队列中，一般存储 原序列的下标 即可，而不需要存储原序列的值，根据保序性，存储的下标一定是单调递增的；

单调队列中的元素是 原序列的下标，对应到原序列时，根据求解问题的不同，当需要求最大值时，它是单调递减的；当需要求最小值时，它是单调递增的；

继续回到上文提到的滑动窗口中的最大值问题。

【例题1】给定一个长度为 整数数组 ，有一个大小为 的滑动窗口从数组的最左侧移动到数组的最右侧。只能看到在滑动窗口内的 个数字。滑动窗口每次只向右移动一位。返回滑动窗口中的最大值。

我们要实现的，就是把原序列 中的元素逐个执行单调队列的 插入 操作。当 插入 的原序列的下标为 $i$ 时，期望是单调队列中的元素从 队首 到 队尾 都在原序列的区间 为右端点，长度为 的区间内），且对应到原序列的值单调递减，这样每次插入完毕，就可以在 的时间内，从队首获取到最大值（即区间 内的最大值）。

为什么是单调递减？而不是单调递增？

对于每个需要插入的下标 ，队尾的元素为原序列的下标 ，则根据保序性，一定能够满足 ，如果对应到原序列中，满足 ，那么 不会比 更优，原因是：对于区间 来说， 一定在区间内，而 则未必，也就是说 下标 没必要存储到单调队列中。于是对于单调队列中的存储的元素 需要满足： ，即 维护一个单调递减的队列。

实际执行过程中，每次插入后，队尾元素 减去 队首元素 必须小于等于 ，一旦超过 ，就要从队首不断出队了。

【例题2】给定一个下标从 0 开始，元素个数为 的整数数组 和一个整数 。开始在下标 0 处。每一步，最多可以往前跳 步，但不能跳出数组的边界。也就是说，可以从下标 跳到 包含 两个端点的任意位置。
目标是到达数组最后一个位置（下标为 ），得分 为经过的所有数字之和，求得分的最大值。

比较容易想到的是动态规划，假设跳到位置 的最大值是 ， 那么一定是从 中的某个位置跳过来的，可以得到状态转移方程如下：

但是这一步的问题在于，数组长度为 时，每次状态转移的时间为 ，所以整個算法的时间复杂度为 。所以我们需要想办法将 这步操作化为 。
维护一个单调递减的队列，这样就能通过 的时间找到从队首找到最大值。单调队列始终保持 的元素在队列中是单调递减的。对于队列中的两个元素，下标位置为 , 如果 ，则 不能放入 单调队列中，因为它不会比 更优。并且时刻保证，当前元素插入单调队列之后，单调队列队列的

【例题3】返回数组 的最短的非空连续子数组的长度，该子数组的和至少为 。如果没有和至少为 的非空子数组，返回 。

前缀和预处理：令 代表 的前缀和，对于一段左开右闭子数组 ， 就是这段子数组的和，其中 ，并且必须满足子数组和 。
单调性的思考：对于两个下标 ， 如果 ，则 不会比 更优，所以，我们只需要维护一个 值单调递增的单调队列；
维护单调队列：单调队列的队首一定是 值最小的， ，则记录 作为一个候选解，并且弹出队首；
实际落地方案：然后只需要枚举 ，维护 的单调队列，且单调队列插入的是前缀和的下标值，候选最优值 用于和最终最优值进行比较取小者，不存在候选解则返回 。

关于 「 单调队列 」 的内容到这里就结束了。 更多队列相关的内容可以参考我知乎专栏 「 法 」中队列相关的文章。

北航《算法与数据结构》在线作业三

一、单选题（共 25 道试题，共 100 分。）

1. 对下面四个序列用快速排序的方法进行排序，以序列的第一个元素为基础进行划分 。 在第一趟划分过程中，元素移动次数最多的序列是 ()。

2. 设一数列的顺序为1，2，3，4，5，6，通过栈结构不可能排成的顺序数列为（）。

3. 线性表是一个具有n个（）的有限序列。

4. 链表不具有的特点是（ ）。

A. 不必事先估计存储空间

B. 可随机访问任一元素

C. 插入删除不需要移动元素

D. 所需空间与线性表长度成正比

5. 对于线性表基本运算，以下结果是正确的是

A. 初始化INITIATE(L)，引用型运算，其作用是建立一个空表L=Ф

B. 求表长LENGTH(L)，引用型运算，其结果是线性表L的长度

D. 定位LOCATE(L,X), 引用型运算.若L中存在一个或多个值与X相等的结点，运算结果为这些结点的序号的最大值；否则运算结果为0

6. 队列的插入操作是在（ ）进行。

7. 下列有关图遍历的说法中不正确的是（ ）。

A. 连通图的深度优先搜索是个递增过程

B. 图的广度优先搜索中邻接点的寻找具有“先进先出”的特征

C. 非连通图不能用深度优先搜索法

D. 图的遍历要求每个顶点仅被访问一次

8. 若由森林转化得到的二叉树是非空的二叉树，则二叉树形状是 （）。

A. 根结点无右子树的二叉树

B. 根结点无左子树的二叉树

C. 根结点可能有左二叉树和右二叉树

D. 各结点只有一个儿子的二叉树

9. 在所有排序方法中，关键字比较的次数与记录得初始排列次序无关的是（）

10. 对于单链表表示法，以下说法错误的是（ ）

A. 数据域用于存储线性表的一个数据元素

B. 指针域或链域用于存放一个指向本结点所含数据元素的直接后继所在结点的指针

C. 所有数据通过指针的链接而组织成单链表

D. NULL称为空指针，它不指向任何结点，只起标志作用

11. 下列数据组织形式中，（ ）的各个结点可以任意邻接。