洛谷 P1886 【模板】单调队列 / 滑动窗口

题目描述

有一个长为 n 的序列 a，以及一个大小为 k 的窗口。现在这个窗口从左边开始向右滑动，每次滑动一个单位，求出每次滑动后窗口中的最小值和最大值。

例如，对于序列 [1,3,−1,−3,5,3,6,7] 以及 k=3，有如下过程：

窗口位置[1 3 -1] -3 5 3 6 7 1 [3 -1 -3] 5 3 6 7 1 3 [-1 -3 5] 3 6 7 1 3 -1 [-3 5 3] 6 7 1 3 -1 -3 [5 3 6] 7 1 3 -1 -3 5 [3 6 7]​最小值−1−3−3−333​最大值335567​​

输入格式

输入一共有两行，第一行有两个正整数 n,k；
第二行有 n 个整数，表示序列 a。

输出格式

输出共两行，第一行为每次窗口滑动的最小值；
第二行为每次窗口滑动的最大值。

输入输出样例

输入 #1复制

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

输出 #1复制

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

说明/提示

【数据范围】
对于 50% 的数据，1≤n≤105；
对于 100% 的数据，1≤k≤n≤106，ai​∈[−231,231)。

#include<bits/stdc++.h> using namespace std; const int N=1e6+10; int a[N],q[N]; int a1,k; int main() { scanf("%d%d",&a1,&k); for(int i=0;i<a1;i++) scanf("%d",&a[i]); int hh=0,tt=-1; for(int i=0;i<a1;i++) { if(hh<=tt&&i-k+1>q[hh]) hh++; while(hh<=tt&&a[q[tt]]>=a[i]) { tt--; } q[++tt]=i; if(i>=k-1) printf("%d ",a[q[hh]]); } puts(""); hh=0,tt=-1; for(int i=0;i<a1;i++) { if(hh<=tt&&i-k+1>q[hh]) hh++; while(hh<=tt&&a[q[tt]]<=a[i]) { tt--; } q[++tt]=i; if(i>=k-1) printf("%d ",a[q[hh]]); } puts(""); return 0; }