D - 滑动窗口（Week5作业）

题目

给定一个大小为n≤106n≤106的数组。
有一个大小为k的滑动窗口，它从数组的最左边移动到最右边。
您只能在窗口中看到k个数字。
每次滑动窗口向右移动一个位置。
以下是一个例子：
该数组为[1 3 -1 -3 5 3 6 7]，k为3。

您的任务是确定滑动窗口位于每个位置时，窗口中的最大值和最小值。

输入格式

输入包含两行。
第一行包含两个整数n和k，分别代表数组长度和滑动窗口的长度。
第二行有n个整数，代表数组的具体数值。
同行数据之间用空格隔开。

输出格式

输出包含两个。
第一行输出，从左至右，每个位置滑动窗口中的最小值。
第二行输出，从左至右，每个位置滑动窗口中的最大值。

输入样例：

8 3
1 3 -1 -3 5 3 6 7

输出样例

-1 -3 -3 -3 3 3
3 3 5 5 6 7

题目思路：

1、典型的单调队列题目
	·指针 trail 指向队尾,判断新进入窗口的数是否比队尾中的大/小，符合条件入栈（找最大值时，比队尾小入队列，否则，队尾出队列，数据再入队列）
	·指针 head 指向队首，判断当前队首是否在滑动窗口中，若不在head++
2、可以利用数组模拟队列过程，速度更快，处理更方便；
3、可以选择用一个队列记录每次入队列的数组索引，方便 head 指针判断是否弹出队首。

（ps:以后交代码，出现tle记得换个编译器试试，一直tle最后换了个编译器通过了，顺便把之前tle版本也都测试了一下，也ac了。。。惨痛教训）

代码实现：

第一种：

#include<cstdio>
#include<cstring>
using namespace std;
int term[1000005];
int a[1000005];
int n,k;
void windoww(int z)
{
 int head=0;
 int trail=-1;
 for(int i=0;i<n;i++)
 {
  while((z*term[i])>=(z*term[a[trail]]) && trail>=head) trail--;
  a[++trail]=i;
  while(a[head]<=i-k && trail>=head) head++;
  if(i>=k-1) printf("%d ",term[a[head]]);
 }
 printf("\n");
}
int main()
{
 scanf("%d %d",&n,&k);
 for(int j=0;j<n;j++)
  scanf("%d",&term[j]);
 windoww(-1);
 windoww(1);
 return 0;
}

对于实现代码的中间/其他思路：

void windoww(int z,int n,int k)
{
	start=0;
	end=k;
	head=0;
	trail=-1;
	for(int i=0;i<n;i++)
		q[i]=0;
	for(int i=0;i<n;)
	{
		while(i>=start&&i<end)
		{
			if(trail<head)
			{
				trail++;
				q[trail]=term[i];
				i++;
				continue;
			}
			while(z*term[i]>z*q[trail]&&trail>head-1) trail--;
			trail++;
			q[trail]=term[i];
			i++;
		}
		printf("%d ",q[head]);
		start++;
		end++;
		if(q[head]==term[start-1]) head++;
	}
	printf("\n");
}

void windoww(int z)
{
	int head=0;
	int trail=-1;
	for(int i=0;i<n;i++)
	{
		while((z*term[i])>=(z*term[a[trail]]) && trail>=head) trail--;
		a[++trail]=i;
		while(a[head]<=i-k && trail>=head) head++;
		if(i>=k-1) printf("%d ",term[a[head]]);
	}
	printf("\n");
}