题目描述
有一个长为 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; }
