【L258】单调队列

258.1 队列&栈

队列：queue, FIFO

栈：stack, LIFO

258.2 单调队列

258.2.1 题目描述

\qquad给定一个长度为N的序列，以及一个整数K，要求找出该序列所有长度为K的子段里面元素的最大值和最小值。

258.2.2 解题步骤

\qquad我们可以使用RMQ表来完成这道题目，时间复杂度为$O(\log N)$。但是这道题数据范围有一点大，所以不推荐使用。

\qquad现在要学一种新的方法：单调队列，这个数据结构可以用$O(N)$的时间复杂度完成这道题目。

\qquad单调队列和数组一样，只不过他的元素一定是从小到大或者从大到小按照顺序来排列的。

\qquad我们可以维护一下这个单调队列：

\qquad输入样例：1 3 -1 -3 5 3 6 7。

\qquadN=8, K=3

\qquad一开始的时候，单调队列为空(NULL)。

\qquadstep 1：1进入队列 单调队列：1

\qquadstep 2: 3进入队列，此时单调队列的元素个数不超过查询的数目K=3。 单调队列：1 3

\qquadstep 3: -1进入队列，虽然此时单调队列的元素个数不超过查询的个数K=3，但是这个时候对尾元素3小于新加入的元素-1，由于在3出队列的时候，-1还没有出队列，所以3就不会再有用了，因此3出队列，同理，1也要出队列。此时单调队列只剩下一个元素了。单调队列：-1

\qquadstep 4: -3进入队列，和step 3一样，-3比-1晚一些入队列，而且-3<-1，所以-1不会在有用了，-1出队列。 单调队列：-3

\qquadstep 5: 5入队列 单调队列：-3 5

\qquadstep 6: 3入队列，和step 3一样，3比5晚一些入队列，而且3<5，所以5不会再游泳了，5出队列。 单调队列：-3 3

\qquadstep 7: 6入队列 单调队列：-3 3 6

\qquadstep 8: 7入队列，但是这个时候单调队列的长度已经超过了K=3，所以对首元素-3出队，单调队列：3 6 7

\qquad降序和升序一样，只不过是单调队列要反一下

\qquad问题来了：最小（大）值是多少呢？

\qquad其实大家仔细观察一下就可以发现：对首元素每一次都是最小的，那是因为单调队列的性质所致的。所以查询就是对手元素。

\qquad等于是只遍历一遍元素就求出了区间的最小值，而且比RMQ方便许多，所以我推荐使用这种方法，时间复杂度为$O(N)$。

\qquad又：单调队列可以使用Stl里面的deque来实现一下，deque是双端队列，可以访问两边的元素。但是这道题数据范围实在是太大了，不推荐使用deque求解。

\qquad总结：单调队列就是下标单调，值也单调的队列。可以使用deque来实现，头文件为#include \<deque>。

258.2.3 代码

258.2.3.1 STL实现代码

#include <bits/stdc++.h> using namespace std;deque <int> q;int a[1000010];int main() {// 首先来查询区间最小值const char newline = '\n';const char space = ' ';q.clear();int n, k;cin >> n >> k;// 输入序列for(int i = 1; i <= n; i ++) scanf("%d", &a[i]);for(int i = 1; i <= n; i ++){while(! q.empty() && a[q.back()] >= a[i]) // 队列{q.pop_back();}q.push_back(i);while(i - q.front() >= k) q.pop_front();char ch = space;if(i == n) ch = newline;if(i >= k) printf("%d%c", a[q.front()], ch);}q.clear();// 接下来查询区间最大值for(int i = 1;i <= n;i ++){while(! q.empty() && a[q.back()] <= a[i]){q.pop_back();}q.push_back(i);while(i - q.front() >= k) q.pop_front();char ch = space;if(i == n) ch = newline;if(i >= k) printf("%d%c", a[q.front()], ch);}return 0; }

258.2.3.2 手工实现代码

#include <bits/stdc++.h> using namespace std;const int N = 1000010;int q[N], fr, ed; int val[N];bool empty() {return fr == ed; }void clear() {fr = ed = 0; }int main() {int n, k;cin >> n >> k;for(int i = 1; i <= n; i ++){scanf("%d", &val[i]);}clear();for(int i = 1; i <= n; i ++){while(! empty() && val[i] <= val[q[ed - 1]]) ed --;q[ed ++] = i;while(! empty() && i - q[fr] >= k) fr ++;if(i >= k) printf("%d ", val[q[fr]]);}printf("\n");clear();for(int i = 1; i <= n; i ++){while(! empty() && val[i] >= val[q[ed - 1]]) ed --;q[ed ++] = i;while(! empty() && i - q[fr] >= k) fr ++;if(i >= k) printf("%d ", val[q[fr]]);}return 0; }

总结

以上是生活随笔为你收集整理的Lesson258 - 单调队列的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。