队列 | 基本数据结构

参考《算法竞赛进阶指南》、AcWing题库

队列

队列是一种 “先进先出” 的线性数据结构。一般来讲, 元素从右端进入队列 (入队), 从左端离开队列 (出队)。于是我们称队列的左端为队头, 右端为队尾。可以在 $\mathrm{C}++$ 中用一个数组和两个变量 (记录队头和队尾的位置) 来实现队列结构。

元素进行多次入队、出队后, 用于实现队列结构的数组的开头部分空间就会被严重浪费, 所以我们经常将其优化为 “循环队列”, 也就是把队列看作一个首尾相接的环, 只要队列中的元素个数在任意时刻都不超过环长, 那么随着入队和出队操作的进行, 存储元素的那一段位置就像沿着环不停地移动, 重复利用着历史上曾被占用过的空间。 C++ STL 中的 queue 就是一个循环队列, 也是我们在代码中最常见的队列实现方式。
队列还有很多变体。例如两端都能插入或取出元素的双端队列 (C++ STL deque), 给每个元素附带一个评估值、出队时取出估值最大的、等价于一个二叉堆的优先队列 (C++STL priority_queue)。队列也是实现广度优先搜索的基本结构。

---

132. 小组队列

题目描述

有 $n$ 个小组要排成一个队列，每个小组中有若干人。

当一个人来到队列时，如果队列中已经有了自己小组的成员，他就直接插队排在自己小组成员的后面，否则就站在队伍的最后面。

请你编写一个程序，模拟这种小组队列。

输入格式：

输入将包含一个或多个测试用例。

对于每个测试用例，第一行输入小组数量 $t$。

接下来 $t$ 行，每行输入一个小组描述，第一个数表示这个小组的人数，接下来的数表示这个小组的人的编号。

编号是 $0$ 到 $999999$ 范围内的整数。

一个小组最多可包含 $1000$ 个人。

最后，命令列表如下。 有三种不同的命令：

1、ENQUEUE x - 将编号是 $x$ 的人插入队列；

2、DEQUEUE - 让整个队列的第一个人出队；

3、STOP - 测试用例结束

每个命令占一行。

当输入用例 $t=0$ 时，代表停止输入。

需注意：测试用例最多可包含 $200000$（$20$ 万）个命令，因此小组队列的实现应该是高效的：

入队和出队都需要使用常数时间。

输出样例

对于每个测试用例，首先输出一行 Scenario #k，其中 $k$ 是测试用例的编号。

然后，对于每个 DEQUEUE 命令，输出出队的人的编号，每个编号占一行。

在每个测试用例（包括最后一个测试用例）输出完成后，输出一个空行。

数据范围

$1 \le t \le 1000$

输入样例：

2
3 101 102 103
3 201 202 203
ENQUEUE 101
ENQUEUE 201
ENQUEUE 102
ENQUEUE 202
ENQUEUE 103
ENQUEUE 203
DEQUEUE
DEQUEUE
DEQUEUE
DEQUEUE
DEQUEUE
DEQUEUE
STOP
2
5 259001 259002 259003 259004 259005
6 260001 260002 260003 260004 260005 260006
ENQUEUE 259001
ENQUEUE 260001
ENQUEUE 259002
ENQUEUE 259003
ENQUEUE 259004
ENQUEUE 259005
DEQUEUE
DEQUEUE
ENQUEUE 260002
ENQUEUE 260003
DEQUEUE
DEQUEUE
DEQUEUE
DEQUEUE
STOP
0 

输出样例：

Scenario #1
101
102
103
201
202
203

Scenario #2
259001
259002
259003
259004
259005
260001 

算法分析

这是一道非常简单的题目, 因为在任何时刻, 同一个小组的人只要来到了队伍, 就会站在一起, 所以我们建立一个队列 $Q_{0}$ 存储队伍中所有小组的编号, 再为每个小组 $i$ 建立一个队列 $Q_{i}$ 存储队伍中这个小组的所有成员, 一共 $n+1$ 个队列。

当一个编号为 $X$, 组号为 $Y$ 的人来到队伍时, 我们直接把 $X$ 插入 $Q_{Y}$ 末尾。如果在插入之前 $Q_{Y}$ 是空的, 则还要把 $Y$ 插入到 $Q_{0}$ 末尾, 表明队伍最后出现了一个新的小组。

当接收到出队指令时, 我们通过 $Q_{0}$ 得知排在最前面的小组组号 $Y$, 然后再把 $Q_{Y}$ 的队头出队。出队后如果 $Q_{Y}$ 为空, 就从 $Q_{0}$ 开头删除 $Y$, 表明这个小组目前所有人已经离开。

Solution

---

133. 蚯蚓

题目描述

蛐蛐国最近蚯蚓成灾了！

隔壁跳蚤国的跳蚤也拿蚯蚓们没办法，蛐蛐国王只好去请神刀手来帮他们消灭蚯蚓。

蛐蛐国里现在共有 $n$ 只蚯蚓，第 $i$ 只蚯蚓的长度为 $a_i$ ，所有蚯蚓的长度都是非负整数，即可能存在长度为 $0$ 的蚯蚓。

每一秒，神刀手会在所有的蚯蚓中，准确地找到最长的那一只，将其切成两段。

若有多只最长的，则任选一只。

神刀手切开蚯蚓的位置由有理数 $p$ 决定。

一只长度为 $x$ 的蚯蚓会被切成两只长度分别为 $\lfloor px \rfloor$ 和 $x - \lfloor px \rfloor$ 的蚯蚓。

特殊地，如果这两个数的其中一个等于 $0$，则这个长度为 $0$ 的蚯蚓也会被保留。

此外，除了刚刚产生的两只新蚯蚓，其余蚯蚓的长度都会增加一个非负整数 $q$。

蛐蛐国王知道这样不是长久之计，因为蚯蚓不仅会越来越多，还会越来越长。

蛐蛐国王决定求助于一位有着洪荒之力的神秘人物，但是救兵还需要 $m$ 秒才能到来。

蛐蛐国王希望知道这 $m$ 秒内的战况。

具体来说，他希望知道：

1. $m$ 秒内，每一秒被切断的蚯蚓被切断前的长度，共有 $m$ 个数。
2. $m$ 秒后，所有蚯蚓的长度，共有 $n+m$ 个数。

输入格式

第一行包含六个整数 $n,m,q,u,v,t$，其中：$n,m,q$ 的意义参考题目描述；$u,v,t$ 均为正整数；你需要自己计算 $p=u/v$（保证 $0<u<v$）；$t$ 是输出参数，其含义将会在输出格式中解释。

第二行包含 $n$ 个非负整数，为 $a_1,a_2,…,a_n$，即初始时 $n$ 只蚯蚓的长度。

同一行中相邻的两个数之间，恰好用一个空格隔开。

输出格式

第一行输出 $⌊m/t⌋$ 个整数，按时间顺序，依次输出第 $t$ 秒，第 $2t$ 秒，第 $3t$ 秒，……被切断蚯蚓（在被切断前）的长度。

第二行输出 $⌊(n+m)/t⌋$ 个整数，输出 $m$ 秒后蚯蚓的长度；需要按从大到小的顺序，依次输出排名第 $t$，第 $2t$，第 $3t$，……的长度。

同一行中相邻的两个数之间，恰好用一个空格隔开。

即使某一行没有任何数需要输出，你也应输出一个空行。

请阅读样例来更好地理解这个格式。

数据范围

$1 \le n \le 10^5$,
$0 \le a_i \le 10^8$,
$0 < p < 1$,
$0 \le q \le 200$,
$0 \le m \le 7*10^6$,
$0 < u < v \le 10^9$,
$1 \le t \le 71$

输入样例：

3 7 1 1 3 1
3 3 2 

输出样例：

3 4 4 4 5 5 6
6 6 6 5 5 4 4 3 2 2 

样例解释

样例中，在神刀手到来前：$3$ 只蚯蚓的长度为 $3,3,2$。

$1$ 秒后：一只长度为 $3$ 的蚯蚓被切成了两只长度分别为 $1$ 和 $2$ 的蚯蚓，其余蚯蚓的长度增加了 $1$。最终 $4$ 只蚯蚓的长度分别为 $(1,2),4,3$。 括号表示这个位置刚刚有一只蚯蚓被切断。

$2$ 秒后：一只长度为 $4$ 的蚯蚓被切成了 $1$ 和 $3$。$5$ 只蚯蚓的长度分别为：$2,3,(1,3),4$。

$3$ 秒后：一只长度为 $4$ 的蚯蚓被切断。$6$ 只蚯蚓的长度分别为：$3,4,2,4,(1,3)$。

$4$ 秒后：一只长度为 $4$ 的蚯蚓被切断。$7$ 只蚯蚓的长度分别为：$4,(1,3),3,5,2,4$。

$5$ 秒后：一只长度为 $5$ 的蚯蚓被切断。$8$ 只蚯蚓的长度分别为：$5,2,4,4,(1,4),3,5$。

$6$ 秒后：一只长度为 $5$ 的蚯蚓被切断。$9$ 只蚯蚓的长度分别为：$(1,4),3,5,5,2,5,4,6$。

$7$ 秒后：一只长度为 $6$ 的蚯蚓被切断。$10$ 只蚯蚓的长度分别为：$2,5,4,6,6,3,6,5,(2,4)$。

所以，$7$ 秒内被切断的蚯蚓的长度依次为 $3,4,4,4,5,5,6$。

$7$ 秒后，所有蚯蚓长度从大到小排序为 $6,6,6,5,5,4,4,3,2,2$。

算法分析

如果 $q=0$, 即蚯蚓不会变长, 那么本题相当于维护一个集合, 支持查询最大值、 删除最大值、插入新的值。这是二叉堆或 STL set 能够完成的基本操作, 时间复杂度约为 $O(m \log n)$ 。

当 $q>0$ 时, 除了最大值拆成的两个数之外, 集合中的其他数都会增加 $q$ 。设最大值为 $x$ 。我们不妨认为产生了两个大小为 $\lfloor p x\rfloor-q$ 和 $x-\lfloor p x\rfloor-q$ 的新数, 然后再 把整个集合都加上 $q$ 。这与之前的操作是等价的。

于是, 我们可以维护一个变量 $delta$ 表示整个集合的 “偏移量”, 集合中的数加上 $delta$ 是它的真实数值。起初, $delta =0$ 。对于每一秒:

1. 取出集合中的最大值 $x$, 令 $x=x+ delta$。

2. 把 $\lfloor p x\rfloor- delta -q$ 和 $x-\lfloor p x\rfloor- delta -q$ 插入集合。

3. 令 $delta = delta +q$ 。

重复上述步骤 $m$ 轮, 即可得到最终集合中所有数的值。然而, 本题中 $m$ 的范围 过大, 我们需要一种线性算法来更快地求解。

注意到 $p, q$ 是固定常数, $0<p<1$ 且 $q$ 是非负整数。设 $x_{1}, x_{2}$ 为非负整数, 当 $x_{1} \geq x_{2}$ 时, 有 $\left\lfloor p x_{1}\right\rfloor+q=\left\lfloor p x_{1}+q\right\rfloor \geq\left\lfloor p x_{2}+p q\right\rfloor=\left\lfloor p\left(x_{2}+q\right)\right\rfloor$ 。上式第一个等号 成立的原因是整数可以自由移入、移出取整符号而不改变式子的值。

又因为 $x_{1}-x_{2} \geq p\left(x_{1}-x_{2}\right)$, 所以 $x_{1}-p x_{1} \geq x_{2}-p x_{2} \geq x_{2}-p\left(x_{2}+q\right)$ 。进一 步有 $x_{1}-\left\lfloor p x_{1}\right\rfloor+q=\left\lfloor x_{1}-p x_{1}\right\rfloor+q \geq\left\lfloor x_{2}-p\left(x_{2}+q\right)\right\rfloor+q=x_{2}+q-\left\lfloor p\left(x_{2}+q\right)\right\rfloor$ 。
上面两段分析的意义是: 若 $x_{1}$ 在 $x_{2}$ 之前被取出集合, 则在一秒以后, $x_{1}$ 分成 的两个数 $\left\lfloor p x_{1}\right\rfloor+q$ 和 $x_{1}-\left\lfloor p x_{1}\right\rfloor+q$ 分别不小于 $x_{2}+q$ 分成的两个数 $\left\lfloor p\left(x_{2}+q\right)\right\rfloor$ 和 $x_{2}+q-\left\lfloor p\left(x_{2}+q\right)\right\rfloor$ 。换言之, 不仅从集合中取出的数是单调递减的, 新产生的两类数值也分别随着时间单调递减。

我们可以建立三个队列 $A, B, C$, 共同构成需要维护的集合。队列 $A$ 保存初始的 $n$ 个数, 从大到小排序。队列 $B$ 保存每秒新产生的 $\lfloor p x\rfloor$ 那一段数值。队列 $C$ 保存每 秒新产生的 $x-\lfloor p x\rfloor$ 那一段数值。起初队列 $B, C$ 为空, 新产生的数从队尾插入。根 据之前的结论, $B, C$ 单调递减。因此, 每个时刻集合中最大的数就是队列 $A, B, C$ 的三 个队首之一。再配合集合的偏移量 $delta$, 整个算法的时间复杂度为 $O(m+n \log n)$ 。

Solution

---

134. 双端队列

题目描述

达达现在碰到了一个棘手的问题，有 $N$ 个整数需要排序。

达达手头能用的工具就是若干个双端队列。

她从 $1$ 到 $N$ 需要依次处理这 $N$ 个数，对于每个数，达达能做以下两件事：

1．新建一个双端队列，并将当前数作为这个队列中的唯一的数；

2．将当前数放入已有的队列的头之前或者尾之后。

对所有的数处理完成之后，达达将这些队列按一定的顺序连接起来后就可以得到一个非降的序列。

请你求出最少需要多少个双端序列。

输入格式

第一行输入整数 $N$，代表整数的个数。

接下来 $N$ 行，每行包括一个整数 $D_i$，代表所需处理的整数。

输出格式

输出一个整数，代表最少需要的双端队列数。

数据范围

$1 \le N \le 200000$

输入样例：

6
3
6
0
9
6
3 

输出样例：

2 

算法分析

这个问题很难直接求解, 因为在不知道后面会有哪些数的情况下, 我们作出的局部决策很可能造成某个数 $P$ 与 $Q$ 在同一个队列中, 这样只要后面出现了介于 $P$ 和 $Q$ 之间 的数, 不管放到哪里都会导致无解 (无法把队列连成一个有序序列)。这种情况启发我 们, 必须考虑按照数值的大小顺序而不是读入的顺序进行计算。

因为 Sherry 最后会把队列连成一个非降序列, 所以我们不妨反过来思考, 先把 $N$ 个数 $A[1 \sim N]$ 从小到大排序, 然后分成尽量少的几段, 让每一段对应原问题中一个合法的双端队列。

每一段需要满足什么条件才能对应原问题中的双端队列呢? 我们可以依次取出排序后的所有数在原始数组 $A$ 中的下标, 构成一个新的数组 $B$ 。

例如样例数据 $A=[3\;6\;0\;9\;6\;3]$, 下标分别是 $[1\;2\;3\;4\;5\;6]$。
排序后得到 $A^{\prime}=[0\;3\;3\;6\;6\;9]$, 对应原数组下标 $B=\left[\begin{array}{llll}3 & 1 & 6 & 2 & 5 & 4\end{array}\right]$ 。

经过分析可以发现, 如果 $B$ 中的一段满足单谷性质 (先单调递减, 后单调递增), 那么这一段就可以对应为原问题的双端队列 ( $B$ 中保存的是下标, 这一段的谷点就相当于第一个入队, 递减的一段相当于从队头插入, 递增的一段相当于从队尾插入)。

还需要注意的一点是, 如果 $A$ 中存在几个相等的数, 那么这几个数在排序时顺序 是不定的, 我们可以任意交换它们的顺序, 使得 $B$ 数组能够分成更少的段数。

所以我们最终的算法是, 按照 $A^{\prime}$ 中数值的异同, 把 $B$ 看作若干个区间:

$A^{\prime}=[[0],[3\;3],[6\;6],[9]], B=[[3],[1\;6],[2\;5],[4]]$

一个区间一个区间地对 $B$ 进行处理, 最终拼成包含尽量少的段数的序列, 其中每 一段都具有单谷性质。我们可以用一个变量记录当前拼成的序列末尾处于递增状态还 是递减状态, 并用贪心策略尝试把当前区间递增或递减地接在序列末尾。以样例数据为 例:

1. 第一个区间始终看作递减区间插入序列, 当前序列为 $[3]$, 正处于递减状态。
2. 第二个区间 [1 6], 因为 $6>3$, 无法继续递减, 只能以递增形式 [1 6] 插入序 列, 产生拐点, 当前序列为 $[316]$, 正处于递增状态。
3. 第三个区间 [2 5], 因为 $2<6$, 无法继续递增, 只能以递减形式 [5 2] 插入序 列, 产生拐点, 单谷段数加 1 。当前序列为 $[3\;1\;6\;5\;2]$, 正处于递减状态。
4. 第四个区间 [4], 因为 $4>2$, 无法继续递减, 只能以递增形式 [4] 插入序列。

最终得到序列 [3 1 6 5 2 4], 包含 [3 1 6 ], [5 2 4] 两个单谷段, 所以对应到原问题, 需要 2 个双端队列。

Solution

---

单调队列

常用于维护滑动窗口中的最值，单调队列优化DP

// 单调队列求nums数组中长度为 k 的滑动窗口里的最大值
class Solution {
public:
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
        int n = nums.size();
        deque<int> q;
        vector<int> ans;
        for (int i = 0; i < n; ++i) {
            if (q.size() && i - q.front() + 1 > k) q.pop_front();
            while (q.size() && nums[i] >= nums[q.back()]) q.pop_back();
            q.push_back(i);
            if (i >= k - 1) ans.push_back(nums[q.front()]);
        }
        return ans;
    }
};

---

135. 最大子序和

题目描述

输入一个长度为 $n$ 的整数序列，从中找出一段长度不超过 $m$ 的连续子序列，使得子序列中所有数的和最大。

注意： 子序列的长度至少是 $1$。

输入格式

第一行输入两个整数 $n,m$。

第二行输入 $n$ 个数，代表长度为 $n$ 的整数序列。

同一行数之间用空格隔开。

输出格式

输出一个整数，代表该序列的最大子序和。

数据范围

$1 \le n,m \le 300000$

输入样例：

6 4
1 -3 5 1 -2 3 

输出样例：

7 

算法分析

计算 “区间和” 的问题, 一般转化为 “两个前缀和相减” 的形式进行求解。我们先求出 $S[i]$ 表示序列里前 $i$ 项的和, 则连续子序列 $[L, R]$ 中数的和就等于 $S[R]-$ $S[L-1]$ 。那么原问题可以转化为: 找出两个位置 $x, y$, 使 $S[y]-S[x]$ 最大并且 $y- x \leq M$ 。

首先我们枚举右端点 $i$ , 当 $i$ 固定时, 问题就变为: 找到一个左端点 $j$, 其中 $j \in[i-m, i-1]$ 并且 $S[j]$ 最小。

不妨比较一下任意两个位置 $j$ 和 $k$, 如果 $k<j<i$ 并且 $S[k] \geq S[j]$, 那么对于所有大于等于 $i$ 的右端点, $k$ 永远不会成为最优选择。这是因为不但 $S[k]$ 不小于 $S[j]$, 而且 $j$ 离 $i$ 更近, 长度更不容易超过 $M$, 即 $j$ 的生存能力比 $k$ 更强。所以当 $j$ 出现后, $k$ 就完全是一个无用的位置。

以上比较告诉我们, 可能成为最优选择的策略集合一定是一个 “下标位置递增、对应的前缀和 $S$ 的值也递增” 的序列。我们可以用一个队列保存这个序列。随着右端点变从前向后扫描, 我们对每个 $i$ 执行以下三个步骤:

1. 判断队头决策与 $i$ 的距离是否超出 $M$ 的范围, 若超出则出队。
2. 此时队头就是右端点为 $i$ 时, 左端点 $j$ 的最优选择。
3. 不断删除队尾决策, 直到队尾对应的 $S$ 值小于 $S[i]$ 。然后把 $i$ 作为一个新的决策入队。

int l = 1, r = 1;
q[1] = 0; // save choice j=0
for(int i = 1; i <= n; i++) {
	while (l <= r && q[l] < i - m) l++;
	ans = max(ans, sum[i] - sum[q[l]]);
	while (l <= r && sum[q[r]] >= sum[i]) r--;
	q[++r] = i;
}

这就是著名的单调队列算法, 因为每个元素至多入队一次、出队一次, 所以整个算法的时间复杂度为 $O(N)$ 。它的思想也是在决策集合 (队列) 中及时排除一定不是最优解的选择。单调队列是优化动态规划的一个重要手段。

Solution

---

154. 滑动窗口里的最值

题目描述

给定一个大小为 $n \le 10^6$ 的数组。

有一个大小为 $k$ 的滑动窗口，它从数组的最左边移动到最右边。

你只能在窗口中看到 $k$ 个数字。

每次滑动窗口向右移动一个位置。

以下是一个例子：

该数组为 [1 3 -1 -3 5 3 6 7]，$k$ 为 $3$。

窗口位置	最小值	最大值
[1 3 -1] -3 5 3 6 7	-1	3
1 [3 -1 -3] 5 3 6 7	-3	3
1 3 [-1 -3 5] 3 6 7	-3	5
1 3 -1 [-3 5 3] 6 7	-3	5
1 3 -1 -3 [5 3 6] 7	3	6
1 3 -1 -3 5 [3 6 7]	3	7

你的任务是确定滑动窗口位于每个位置时，窗口中的最大值和最小值。

输入格式

输入包含两行。

第一行包含两个整数 $n$ 和 $k$，分别代表数组长度和滑动窗口的长度。

第二行有 $n$ 个整数，代表数组的具体数值。

同行数据之间用空格隔开。

输出格式

输出包含两个。

第一行输出，从左至右，每个位置滑动窗口中的最小值。

第二行输出，从左至右，每个位置滑动窗口中的最大值。

输入样例：

8 3
1 3 -1 -3 5 3 6 7 

输出样例：

-1 -3 -3 -3 3 3
3 3 5 5 6 7 

算法分析

Solution

#include <iostream>
using namespace std;

const int N = 1e6 + 10;

int a[N];
int q[N], hh = 0, tt = -1;

int main() {
  int n, k;
  cin >> n >> k;
  for (int i = 1; i <= n; ++i) cin >> a[i];
  
  for (int i = 1; i <= n; ++i) {
    if (hh <= tt && i - q[hh] + 1 >k ) ++hh;
    while (hh <= tt && a[i] <= a[q[tt]]) --tt;
    q[++tt] = i;
    if(i < k) continue;
    cout << a[q[hh]] << " ";
  }  
  cout << endl;
  
  hh = 0, tt = -1;
  for (int i = 1; i <= n; ++i) {
    if (hh <= tt && i - q[hh] + 1 > k) ++hh;
    while (hh <= tt && a[i] >= a[q[tt]]) --tt;
    q[++tt] = i;
    if(i < k) continue;
    cout << a[q[hh]] << " ";
  }
}