WIKIOI
wiki(I:)
比赛相关
工具软件
语言基础
算法基础
搜索
动态规划
字符串
数学
数据结构
图论
计算几何
杂项
专题
数据结构部分简介
栈
队列
链表
哈希表
并查集
堆简介
二叉堆
配对堆
左偏树
分块思想
块状数组
块状链表
树分块
Sqrt Tree
单调栈
单调队列
ST 表
树状数组
线段树
李超线段树
区间最值操作 & 区间历史最值
划分树
二叉搜索树简介
Treap
Splay
WBLT
Size Balanced Tree
AVL 树
替罪羊树
笛卡尔树
左偏红黑树
跳表
可持久化数据结构简介
可持久化线段树
可持久化块状数组
可持久化平衡树
可持久化字典树
可持久化可并堆
线段树套线段树
平衡树套线段树
线段树套平衡树
树状数组套主席树
分块套树状数组
K-D Tree
珂朵莉树
Link Cut Tree
Euler Tour Tree
Top Tree
析合树
50 objects
本站非官方,所收集资源均来源于网络。
单调队列 - 数据结构
author: Link-cute, Xeonacid, ouuan 在学习单调队列前,让我们先来看一道例题。 ## 例题 [Sliding Window](http://poj.org/problem?id=2823) 本题大意是给出一个长度为 $n$ 的数组,编程输出每 $k$ 个连续的数中的最大值和最小值。 最暴力的想法很简单,对于每一段 $i \sim i+k-1$ 的序列,逐个比较来找出最大值(和最小值),时间复杂度约为 $O(n \times k)$ 。 很显然,这其中进行了大量重复工作,除了开头 $k-1$ 个和结尾 $k-1$ 个数之外,每个数都进行了 $k$ 次比较,而题中 $100\%$ 的数据为 $n \le 1000000$ ,当 $k$ 稍大的情况下,显然会 TLE。 这时所用到的就是单调队列了。 ## 概念 顾名思义,单调队列的重点分为 "单调" 和 "队列" "单调" 指的是元素的的 "规律"——递增(或递减) "队列" 指的是元素只能从队头和队尾进行操作 Ps. 单调队列中的 "队列" 与正常的队列有一定的区别,稍后会提到 ## 例题分析 有了上面 "单调队列" 的概念,很容易想到用单调队列进行优化。 要求的是每连续的 $k$ 个数中的最大(最小)值,很明显,当一个数进入所要 "寻找" 最大值的范围中时,若这个数比其前面(先进队)的数要大,显然,前面的数会比这个数先出队且不再可能是最大值。 也就是说——当满足以上条件时,可将前面的数 "弹出",再将该数真正 push 进队尾。 这就相当于维护了一个递减的队列,符合单调队列的定义,减少了重复的比较次数,不仅如此,由于维护出的队伍是查询范围内的且是递减的,队头必定是该查询区域内的最大值,因此输出时只需输出队头即可。 显而易见的是,在这样的算法中,每个数只要进队与出队各一次,因此时间复杂度被降到了 $O(N)$ 。 而由于查询区间长度是固定的,超出查询空间的值再大也不能输出,因此还需要 site 数组记录第 $i$ 个队中的数在原数组中的位置,以弹出越界的队头。 例如我们构造一个单调递增的队列会如下: 原序列为: ```text 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}` | | -3 已经在窗体外,所以 -3 出队;6 比 3 大,6 入队 | `{3 6}` | | 7 比 6 大,7 入队 | `{3 6 7}` | ### "例题参考代码" ```cpp #include
#include
#include
#include
#define maxn 1000100 using namespace std; int q[maxn], a[maxn]; int n, k; void getmin() { int head = 0, tail = 0; for (int i = 1; i < k; i++) { while (head <= tail && a[q[tail]] >= a[i]) tail--; q[++tail] = i; } for (int i = k; i <= n; i++) { while (head <= tail && a[q[tail]] >= a[i]) tail--; q[++tail] = i; while (q[head] <= i - k) head++; printf("%d ", a[q[head]]); } } void getmax() { int head = 0, tail = 0; for (int i = 1; i < k; i++) { while (head <= tail && a[q[tail]] <= a[i]) tail--; q[++tail] = i; } for (int i = k; i <= n; i++) { while (head <= tail && a[q[tail]] <= a[i]) tail--; q[++tail] = i; while (q[head] <= i - k) head++; printf("%d ", a[q[head]]); } } int main() { scanf("%d%d", &n, &k); for (int i = 1; i <= n; i++) scanf("%d", &a[i]); getmin(); printf("\n"); getmax(); printf("\n"); return 0; } ``` Ps. 此处的 "队列" 跟普通队列的一大不同就在于可以从队尾进行操作,STL 中有类似的数据结构 deque。