学习系列——单调队列 I —— 构建单调递增队列
Description
【知识点】顾名思义，单调队列的重点分为 "单调" 和 "队列"。"单调" 指的是元素的的 "规律"——递增（或递减）。"队列" 指的是元素只能从队头和队尾进行操作。
例如原序列为：1, 3, −1, −3, 5, 3, 6, 7。我们构造一个单调递增的队列会如下：
|
操作 |
队列状态 |
|
1入队 |
{1} |
|
3比1大，3入队 |
{1 3} |
|
−1比队列中所有元素小，所以清空队列−1入队 |
{−1} |
|
−3比队列中所有元素小，所以清空队列−3入队 |
{−3} |
|
5比−3大，直接入队 |
{−3 5} |
|
3比5小，5出队，3入队 |
{−3 3} |
|
6比3大，6入队 |
{−3 3 6} |
|
7比6大，7入队 |
{−3 3 6 7} |
单调队列一般有三步操作：
1、和普通队列不同，单调队列中插入元素的时候，要保证队列的单调性。
2、插入数据。
3、有不少题目对队列的空间有限制，插入数据后，还要维护队列的空间不超过限制。
在 OI 中，一般在单调队列中保存的是数组下标。数据保存在数组 a 中。
单调队列的实现，有两种方法。
方法一：使用 STL 的 双端队列 deque。
维护单调性
while (!que.empty() && a[que.back()]>=a[i]) {
que.pop_back();
}
插入数据
que.push_back(i);维护队列空间限制
while (que.size()>m) {
que.pop_front();
}
方法二：使用数组定义数据
const int MAXN=1e6+10;//数组大小要足够 int que[MAXN];//保存数据 int head=1;//头节点 int tail=0;//尾节点维护单调性
while (head<=tail && que[tail]>=a[i]) {
tail--;
}
入队
que[++tail]=i;维护空间大小不操过m
while (head<=tail&&tail-head+1>m) {
head++;
}
【任务】给一个长度为 n 的队列 a，请从头到尾输出对应的单调递增队列。
Input Format
第一行包括一个整数 n (2≤n≤10^6)，表示队列 a 的大小。第二行包括 n 个整数 −10^9≤ai≤10^9。
Output Format
一共 n 行，每行若干个数。第 i 行表示队列 a1, a2, …, ai 构成的单调递增队列。8
1 3 -1 -3 5 3 6 71
1 3
-1
-3
-3 5
-3 3
-3 3 6
-3 3 6 7