WEEK5 作业 D - 滑动窗口

D - 滑动窗口

题目描述

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

题解

• 采用单调队列的思想。
• 一个数组a 存放长度为n的数列。双向队列b,s用于寻找窗口k中的最大数和最小数。以单调递增队列找出最小值为例。循环n次，依次将n个数加入队列，加入队列尾时，若队列尾元素大于要加入的元素，则将队列尾元素删除，删除至队列为空或队列尾元素小于要加入元素，将当前元素下标i加入队列尾。检查当前队列中队首元素（最小元素）的下标是不是i-k（该元素随窗口移动应删除），若是则将该元素删除。此时队列首元素即为本次k窗口的最小值并输出该最小值。同理找出最大值。

代码

#include <iostream>
#include <stdio.h>
#include <queue>
using namespace std;
int a[1001000];
deque<int>b;
deque<int>s;
int n,k;
int main(int argc, char** argv) {
	int n,k;
	scanf("%d %d",&n,&k);
	for(int i=0;i<n;i++){
		scanf("%d",&a[i]);
	}
	for(int i=0;i<n;i++){
		//入队列，找出最小 
		while(!s.empty()&&a[s.back()]>a[i]){s.pop_back();}
		s.push_back(i);
		if(s.front()==i-k){s.pop_front();}
		if(i>=k-1){printf("%d ",a[s.front()]);}
	} 
	printf("\n");
	for(int i=0;i<n;i++){
		//入队列，找出最大 
		while(!b.empty()&&a[b.back()]<a[i]){b.pop_back();}
		b.push_back(i);
		if(b.front()==i-k){b.pop_front();}
		if(i>=k-1){printf("%d ",a[b.front()]);}
	}
	return 0;
}