单调队列 —— 滑动窗口
dequeue双向队列
dequeue<int>que;//创建双向队列 que.push_front()//在队列前面塞一个元素 que.push_back()//在队列后面塞一个元素 que.pop_front()//删除队列第一个元素 que.pop_back()//删除队列的最后一个元素 que.clear()//清空队列 que.empty()//判断是否为空 que.size()//返回队列元素个数
单调队列
问题：
对每个长度为k的滑动窗体，求其最大值和最小值
思路1:
使出秘技dequeue （STL赛高！）
这里根据雨巨生动形象的例子，我来简单描述一下下：
题意：给出各届acmer的实力，众所周知大学基本上是四年，所以我们滑动窗口的大小就是4，问每个窗口中实力最强与最弱的是多少
举个样例：1 4 6 3 3 3 2
我们现在先求最大值，最小值在最大值的基础上改一改就行。
首先我们看给1入队列（是dequeue，后面不赘述），因为没到达四个元素，所以不输出，再到第二个元素4，大于1，说明在4的伟大作用下，1已经废了，就直接扔出去，也就是“去尾”，得到队列 4 。再到6，6 > 4，所以在6的存在下，4 废了，扔出去，得到队列 6。再到3，3 小于6，说明他有机会，因为可以等到6的退役了（也就是6滑出窗口了），他就可能是最大的，把 3塞进去，得到6，3的队列，现在达到窗口的大小，所以输出队头6，再看3，等于队列尾的元素，就把他也塞进去，再输出一个6，下一个3塞进来以后，我们判断发现队列头还没有出窗口，就再输出6，到了2，塞进去，发现6已经出了窗口，就得“去头”，所以输出3
总结一下，实现单调队列，主要分四个部分：
- 去尾：队尾元素出队列。当有新的acmer等待入队时，需要从队尾开始判断会不会破坏队的单调性，会的话就去尾。
- 入队：将新队员从队尾塞进来
- 去头：队头元素出队列。当acmer满四年后就得退役，也就是要将其扔出队列
- 取解：取队头元素
#include <cstdio>
#include <cstring>
#include <string>
#include <cmath>
#include <iostream>
#include <algorithm>
#include <vector>
#include <stack>
#include <queue>
#include <stdlib.h>
#include <sstream>
#include <map>
#include <set>
using namespace std;
#define inf 0x3f3f3f3f
#define MAX 1000000 + 5
typedef long long ll ;
inline int IntRead(){//int的快读
char ch = getchar();
int s = 0, w = 1;
while(ch < '0' || ch > '9'){
if(ch == '-') w = -1;
ch = getchar();}
while(ch >= '0' && ch <= '9'){
s = s * 10 + ch - '0';
ch = getchar();}
return s * w;
}
int tr[MAX];
int main()
{
int n, k;
deque<int>q;//双向队列
cin>>n>>k;
for(int i = 1; i <= n; i++)
tr[i] = IntRead();
for(int i = 1; i <= n; ++i){
while (!q.empty() && tr[i] < tr[q.back()]) {
q.pop_back();//去尾
}
q.push_back(i);//入队
if(i >= k){//从第k个开始，后面都得输出
while (!q.empty() && i - q.front() + 1 > k) {
q.pop_front();//去头
}
if(i == k) cout<<tr[q.front()];//控制空格的输出
else cout<<' '<<tr[q.front()];
}
}
cout<<endl;
q.clear();//清空队列
for(int i = 1; i <= n; i++){
while (!q.empty() && tr[q.back()] < tr[i]) {
q.pop_back();
}
q.push_back(i);
if(i >= k){
while (!q.empty() && i - q.front() + 1 > k) {
q.pop_front();
}
if(i == k)
cout<<tr[q.front()];
else
cout<<' '<<tr[q.front()];
}
}
cout<<endl;
}
思路2:
手写队列
head代表队列头，tail代表队列尾
结构体的q数组即为“双向队列”，其id用来记录下标，val来记录值
还是那四步，去尾入队去头取解。
#include <cstdio>
#include <cstring>
#include <string>
#include <cmath>
#include <iostream>
#include <algorithm>
#include <vector>
#include <stack>
#include <queue>
#include <stdlib.h>
#include <sstream>
#include <map>
#include <set>
using namespace std;
#define inf 0x3f3f3f3f
#define MAX 1000000 + 5
typedef long long ll ;
inline int IntRead(){//int的快读
char ch = getchar();
int s = 0, w = 1;
while(ch < '0' || ch > '9'){
if(ch == '-') w = -1;
ch = getchar();}
while(ch >= '0' && ch <= '9'){
s = s * 10 + ch - '0';
ch = getchar();}
return s * w;
}
int tr[MAX], n, k;
struct ran{
int id, val;
}q[MAX];
void getmin(){
int head = 1, tail = 0;//初始化
for(int i = 1; i <= n; ++i){
while (head <= tail && tr[i] < q[tail].val) tail--;//去尾
q[++tail].id = i;//入队的时候记得要记录两部分
q[tail].val = tr[i];
while (i - q[head].id + 1 > k) head++;//去头
if(i >= k){
if(i == k)cout<<q[head].val;//控制空格，防止PE
else cout<<' '<<q[head].val;
}
}
cout<<endl;
}
void getmax(){
int head = 1, tail = 0;
for(int i = 1; i <= n; ++i){
while (head <= tail && q[tail].val < tr[i]) tail--;
q[++tail].id = i;
q[tail].val = tr[i];
while (i - q[head].id + 1 > k) head++;
if(i >= k){
if(i == k)cout<<q[head].val;
else cout<<' '<<q[head].val;
}
}
cout<<'\n';
}
int main()
{
cin>>n>>k;
for(int i = 1; i <= n; ++i) tr[i] = IntRead();
getmin();
getmax();
return 0;
} 我看了一下这两个的时间差的不多，2ms，我感觉还是dequeue好写一些，嘎嘎，感觉写成函数更美观一点哎=(^.^)=