Sliding Window

Sliding Window

分为两个主要模块，要在一个滑动窗口中找最小值，以及最大值。

那么你需要去维护两个单调队列，一个是单调递增的队列，一个是单调递减的队列！

得到最小值：

//要写一个单调递增的单调队列得到最小值
void getMin()
{
	memset(que, 0, sizeof(que));
	que[0].value=-INF;
	int r=1,l=1;
	for(int i=1;i<=k;i++){
		while(que[r].value>=arr[i]&&l<=r){//单调递增
			r--;
		}
		que[++r].value=arr[i];//入队
		que[r].pos=i;
	}
	for(int i=k;i<=n;i++){
		while(que[r].value>=arr[i]&&l<=r){//单调递增
			r--;
		}
		que[++r].value=arr[i];//入队
		que[r].pos=i;
		while(que[l].pos<=i-k){
			l++;
		}
		printf("%d ",que[l].value);
	}
}

得到最大值

void getMax()
{
	memset(que, 0, sizeof(que));
	que[0].value=INF;
	int r=1,l=1;
	for(int i=1;i<=k;i++){
		while(que[r].value<=arr[i]&&l<=r){//单调递增
			r--;
		}
		que[++r].value=arr[i];//入队
		que[r].pos=i;
	}
	for(int i=k;i<=n;i++){
		while(que[r].value<=arr[i]&&l<=r){//单调递增
			r--;
		}
		que[++r].value=arr[i];//入队
		que[r].pos=i;
		while(que[l].pos<=i-k){
			l++;
		}
		printf("%d ",que[l].value);
	}
}

ac代码：

#include 
#include
#include 
using namespace std;

const int maxn = 1e6+10;
const int INF = 0x3f3f3f3f;

int n,k;
//开一个结构体，存位置和数值
struct node{
	int pos;
	int value;
}que[maxn];
//开一个数组存要存的num
int arr[maxn];
//要写一个单调递增的单调队列得到最小值
void getMin()
{
	memset(que, 0, sizeof(que));
	que[0].value=-INF;
	int r=1,l=1;
	for(int i=1;i<=k;i++){
		while(que[r].value>=arr[i]&&l<=r){//单调递增
			r--;
		}
		que[++r].value=arr[i];//入队
		que[r].pos=i;
	}
	for(int i=k;i<=n;i++){
		while(que[r].value>=arr[i]&&l<=r){//单调递增
			r--;
		}
		que[++r].value=arr[i];//入队
		que[r].pos=i;
		while(que[l].pos<=i-k){
			l++;
		}
		printf("%d ",que[l].value);
	}
}
//要写一个单调递减的单调队列得到最大值
void getMax()
{
	memset(que, 0, sizeof(que));
	que[0].value=INF;
	int r=1,l=1;
	for(int i=1;i<=k;i++){
		while(que[r].value<=arr[i]&&l<=r){//单调递增
			r--;
		}
		que[++r].value=arr[i];//入队
		que[r].pos=i;
	}
	for(int i=k;i<=n;i++){
		while(que[r].value<=arr[i]&&l<=r){//单调递增
			r--;
		}
		que[++r].value=arr[i];//入队
		que[r].pos=i;
		while(que[l].pos<=i-k){
			l++;
		}
		printf("%d ",que[l].value);
	}
}

int main() {
	scanf("%d%d",&n,&k);
	for(int i=1;i<=n;i++){
		scanf("%d",&arr[i]);
	}
	getMin();
	printf("n");
	getMax();
	return 0;
}