啥是单调队列:
单调队列主要用于求取一个区间的最大最小值。
滑动窗口是一个特别特别经典的题!!!
题目描述
原题来自: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]]<<" ";
}
}
}
还不是很理解,不太可能独立写出来,下星期要记得理解!!!!