研究了一下午，可算是把 滑动窗口 整明白了，下面是来自初学者 的 非常完美 的 总结。
因为在网上找了好久也没有一篇像样的总结，所以励志自己要写一篇！
题目链接：
POJ 2823
题目大意：
输入一个长度为n（n≤≤106106）的数列，给定一个长度为k的窗口，让这个窗口在数列上移动，求移动到每个位置窗口中包含数的最大值和最小值。即设序列为A1A1,A2A2,…,AnAn，设f(i)=min{Ai−k+1Ai−k+1,Ai−k+2Ai−k+2,…,AkAk} ,g(i)=max{Ai−k+1Ai−k+1,Ai−k+2Ai−k+2,…,AkAk}
求：f(k),f(k+1),…,f(n) g(k),g(k+1),…,g(n).
引入：
①简单来说，这个题就是求从i开始的 区间长度 为 k 中的最小值。
②所以，我们可以对这个题目进行模拟，用一个最大值和最小值记录当前起点为i，长度为k 中的最大最小值(这个代码就不写了)。
③但是，复杂度为O(N*K),如果N与K都很大，那么就会超时，所以我们就来看一下更高效的方法！
一、理解滑动窗口的思想
样本序列={4,3,5,6,7} n=5,k=2
① 我们首先分析，刚刚超时的原因，我们对一个序列进行模拟时(以样本数据为例)，分析第一个元素时，分析到了第二个元素，然后我们分析第二个元素时，又把第二个元素分析一遍，如果k！=2，而是等于一个10000+的数，我们每次分析的时候，重叠的部分就越大，我们做的无用功也就越多。怎么进行优化呢？
②(敲重点!)我们先不引入算法，先引入模型，我们可以对一段序列这么分析(样本序列为例):
1).[4,3],5,6,7 然后我们抛弃第一个元素，引入第3个元素
2).4,[3,5],6,7,依次我们抛弃第二个元素，引入第4个元素
3).4,3,[5,6],7 依次我们抛弃第三个元素，引入第5个元素
这样我们从2开始访问，就可以通过每次抛弃一个过时元素，引入一个新元素而达到遍历 全部 k区间的 值。
③通过上述分析，我们只需要将我们遍历过程中的每一个新区间内的最大值最小值求出来即可，要怎么做呢？我们就需要维护一个单调队列：
1).单调队列指的是，队列中的元素都是递增或者递减的，因而我们输出对首元素就是当前的最小值或者最大值。
2).所以说我们需要根据上述模型的引入进行刚刚的操作，但是我们需要构建一个单调的队列，怎么构建呢？根据以下方法：
假设我们求的是最小值，所以我们让队首元素保持最小值。
下面会产生两种情况：
1).新来的元素比队尾的元素大，我们就直接把它放到队列末尾。
2).新来的元素比队尾的元素小，我们就一直扔掉队尾元素，直到队列为空或者队尾元素比新来的元素小时，把他放到队尾。
这里解释一下为什么：
第一种情况：因为我们首元素维护的最小值，所以如果新来的元素比队尾的元素大，新来的元素是有可能成为最小值的。因为我们会一步步的舍弃掉队首元素，这样新来的元素绝对可以成为某个区间的最小值。
第二种情况：假设现在区间里有1,4,新元素是3，我们如果把3放进去，则会产生新序列1,4,3但是这个4在他离开之前也不可能成为最小值，(除非k=1）,所以这个时候我们说 这个 4是无用的，我们应该及时删除。
④这样我们就可以实现区间最小值的记录。
二、数组模拟法实现滑动窗口
1).需要两个指针，一个指向队首元素，另一个指向末尾元素，我们用 head与tail表示
2).开始按照上述方法，进行模拟：
//以最小值为例
scanf("%lld%lld",&n,&m);
for(int i=1;i<=n;i++) scanf("%lld",&a[i]);
q[tail]=1;
num[1]=a[1];//排除如果k=1的情况
for(int i=2;i<=n;i++)//首先从第二个元素开始
{
while((head<=tail)&&(a[i]<a[q[tail]]))//第二种情况，一直找到空或者当前队尾元素小于新来元素
tail--;
q[++tail]=i;//记录数组下标
while((head<=tail)&&(q[head]<i-m+1))//如果当前 队首元素的数组下标小于区间长度i-k+1了，说明当前队首元素过时了，及时更新
head++;
num[i]=a[q[head]];//队首元素一定就是当前的最小值的下标
}
for(int i=m;i<=n;i++) printf("%lld ",num[i]); 我们可以发现，队列里不是存的数而是存的数组的下标，这是便于我们判断当前是否超过区间长度并及时更新。
三、双向队列实现滑动窗口
1).原理是一样的，只不过用到了STL里面的deque(双向队列)，使得这个题目变得异常简单。
2).通过STL我们可以直接对末尾元素进行删除，或者对队首元素进行删除，但是我感觉 数组模拟法还是需要懂得，毕竟那是原理嘛。
ll n,m;
ll num[maxn];
ll a[maxn];
int main()
{
deque<int>q;
ll head=1,tail=1;
scanf("%lld%lld",&n,&m);
for(int i=1;i<=n;i++) scanf("%lld",&a[i]);
num[1]=a[1];
q.push_back(1);
for(int i=2;i<=n;i++)
{
while((!q.empty())&&(a[i]<a[q.back()]))//直接判断，与数组模拟思路相同
q.pop_back();
q.push_back(i);
while((!q.empty())&&(q.front()<i-m+1))
q.pop_front();
num[i]=a[q.front()];
}
for(int i=m;i<=n;i++)
printf("%lld ",num[i]);
return 0;
} 由上面代码可以看出，STL不过是把数组模拟的方法简化了但是思路是一样的。
四、附录
附上完整代码的求最大值和最小值的滑动窗口，其实就是把条件改了一下就可以了（以数组模拟为例，因为数组OK了STL不是问题）：
#include <queue>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <iostream>
#include <stack>
#include <algorithm>
#include <vector>
#include <map>
#include <set>
#define MIN(x,y) ((x)<(y)?(x) : (y))
#define MAX(x,y) ((x)>(y)?(x) : (y))
#define PI 3.1415926535
#include <set>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const ll INF=1e10;
const int maxn=1e6+5;
const ll mod=1e9+7;
ll n,m;
ll Max[maxn];
ll a[maxn];
ll Min[maxn];//以cur和head表示 位置
ll q[maxn];
void get_max()
{
int head=1,cur=1;
q[1]=1;
Max[1]=a[1];
for(int i=2;i<=n;i++)//
{
while(head<=cur&&a[q[cur]]<a[i])
cur--;
q[++cur]=i;
while(head<=cur&&q[head]<i-m+1)
head++;
Max[i]=a[q[head]];
}
}
void get_min()
{
memset(q,0,sizeof(q));
int head=1,cur=1;
q[1]=1;
Min[1]=a[1];
for(int i=2;i<=n;i++)//
{
while(head<=cur&&a[q[cur]]>a[i])
cur--;
q[++cur]=i;
while(head<=cur&&q[head]<i-m+1)
head++;
Min[i]=a[q[head]];
}
}
int main()
{
scanf("%lld%lld",&n,&m);
for(int i=1;i<=n;i++) scanf("%lld",&a[i]);
get_min();
get_max();
for(int i=m;i<=n;i++)
printf("%lld ",Min[i]);
printf("\n");
for(int i=m;i<=n;i++)
printf("%lld ",Max[i]);
return 0;
}
不懂可以评论交流，或者私信哦。
京公网安备 11010502036488号