E - 滑动窗口(单调队列)

啥是单调队列:

单调队列主要用于求取一个区间的最大最小值

滑动窗口是一个特别特别经典的题!!!

题目描述

原题来自:POJ 2823

给一个长度为 NN 的数组,一个长为 KK 的滑动窗体从最左端移至最右端,你只能看到窗口中的 KK 个数,每次窗体向右移动一位,如下图:

Window position Minimum value Maximum value
[1  3  -1] -3  5  3  6  7  -1 3
 1 [3  -1  -3] 5  3  6  7  -3 3
 1  3 [-1  -3  5] 3  6  7  -3 5
 1  3  -1 [-3  5  3] 6  7  -3 5
 1  3  -1  -3 [5  3  6] 7  3 6
 1  3  -1  -3  5 [3  6  7] 3 7

你的任务是找出窗体在各个位置时的最大值和最小值。

输入格式

第 1 行:两个整数 NN 和 KK
第 2 行:NN 个整数,表示数组的 NN 个元素(元素大小≤2\times 10^9元素大小≤2×109);

输出格式

第一行为滑动窗口从左向右移动到每个位置时的最小值,每个数之间用一个空格分开;
第二行为滑动窗口从左向右移动到每个位置时的最大值,每个数之间用一个空格分开。

样例

Input Output
8 3
1 3 -1 -3 5 3 6 7
-1 -3 -3 -3 3 3
3 3 5 5 6 7

数据范围与提示

对于 20\%20% 的数据,K≤N≤1000;
对于 50\%50% 的数据,K≤N≤10^5;
对于 100\%100% 的数据,K≤N≤10^6。

其实就是数组模拟队列,用队列模拟了窗口滑动的过程。

#include<bits/stdc++.h>
using namespace std;
long long int n,k,i,j,a[2000101],b[2020200];
int main(){
	cin>>n>>k;
	for(i=1;i<=n;i++){
		cin>>a[i];
	}int t=0,q=-1;//t是队头,q是队尾;
	for(i=1;i<=n;i++){
		if(b[t]<=i-k&&t<=q){
			t++;
		}//想象一下,一个宽为k的正方形,每次移动一下下,直到对头大于队尾
		while(t<=q&&a[i]<=a[b[q]]){
			q--;
		}b[++q]=i;
		if(i>=k){
			cout<<a[b[t]]<<" ";
		} 
	}cout<<endl;
	t=0,q=-1;
	 for(i=1;i<=n;i++){
	 	if(b[t]<=i-k&&t<=q){
	 		t++;
		 }while(t<=q&&a[i]>=a[b[q]]){
		 	q--;}
		 	b[++q]=i;

		 	if(i>=k){
		 		cout<<a[b[t]]<<" ";
			 }
		 }
}

还不是很理解,不太可能独立写出来,下星期要记得理解!!!!

上一篇:卷积神经网络 实战CIFAR10-基于pytorch


下一篇:更新显卡驱动