滑动窗口【区间最大值区间&最小值】【单调队列】

问题描述

ZJM 有一个长度为 n 的数列和一个大小为 k 的窗口, 窗口可以在数列上来回移动. 现在 ZJM 想知道在窗口从左往右滑的时候，每次窗口内数的最大值和最小值分别是多少. 例如：
数列是 [1 3 -1 -3 5 3 6 7], 其中 k 等于 3.

Input

输入有两行。第一行两个整数n和k分别表示数列的长度和滑动窗口的大小，1<=k<=n<=1000000。第二行有n个整数表示ZJM的数列。

Output

输出有两行。第一行输出滑动窗口在从左到右的每个位置时，滑动窗口中的最小值。第二行是最大值。

Sample Input

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

Sample Output

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

问题分析

采用数据结构——单调队列。
单调队列的维护过程与单调栈相似
• 区别在于单调栈只维护一端(栈顶), 而单调队列可以维护两端(队首和队尾) 。单调栈通常维护 全局 的单调性, 而单调队列通常维护 局部 的单调性。单调栈大小没有上限, 而单调队列通常有大小限制。
• 由于单调队列 可以队首出队 以及 前面的元素一定比后面元素先入队 的性质，使得它可以维护局部的单调性。
• 当队首元素不在区间之内则可以出队。
• 时间复杂度与单调栈一致。
如果查找全局的最小值, 可以使用单调栈, 尽管有些多余
• 现在要求查找窗口内的最小值, 是一个 局部 的概念
• 维护一个单调递增队列, 队列中的元素均属于当前窗口
• 当元素不属于当前窗口时, 将队首元素弹出即可
• 可以手动模拟一下整个过程
参考代码如下：

#include<stdio.h>
int a[1000010],m[1000010],q[1000010];//a记录原数组；m记录区间最值；q模拟队列，记录入队下标
int main()
{
	int n,k;
	scanf("%d%d",&n,&k);
	for(int i=1;i<=n;i++)
		scanf("%d",&a[i]);
	//求区间最小值
	int l = 1, r = 0; 
	for(int i = 1; i <= n; i++){
		while(r >= l && a[q[r]] >= a[i]) r--; 
		q[++r] = i; 
		if(q[r]-q[l]+1 > k) l++;
		m[i] = a[q[l]];
	}
	for(int i=k;i<n;i++)
		printf("%d ",m[i]);
	printf("%d\n",m[n]);
	//求区间最大值
	l = 1, r = 0; 
	for(int i = 1; i <= n; i++){
		while(r >= l && a[q[r]] <= a[i]) r--; 
		q[++r] = i; 
		if(q[r]-q[l]+1 > k) l++;
		m[i] = a[q[l]];
	}
	for(int i=k;i<n;i++)
		printf("%d ",m[i]);
	printf("%d",m[n]);	
	return 0;
}