每日一题 第八十八期 洛谷 滑动窗口
滑动窗口 /【模板】单调队列
题目描述
有一个长为 n n n 的序列 a a a，以及一个大小为 k k k 的窗口。现在这个从左边开始向右滑动，每次滑动一个单位，求出每次滑动后窗口中的最大值和最小值。
例如，对于序列 [ 1 , 3 , − 1 , − 3 , 5 , 3 , 6 , 7 ] [1,3,-1,-3,5,3,6,7] [1,3,−1,−3,5,3,6,7] 以及 k = 3 k = 3 k=3，有如下过程：
窗口位置 最小值 最大值 [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 \def\arraystretch{1.2} \begin{array}{|c|c|c|}\hline \textsf{窗口位置} & \textsf{最小值} & \textsf{最大值} \\ \hline \verb![1 3 -1] -3 5 3 6 7 ! & -1 & 3 \\ \hline \verb! 1 [3 -1 -3] 5 3 6 7 ! & -3 & 3 \\ \hline \verb! 1 3 [-1 -3 5] 3 6 7 ! & -3 & 5 \\ \hline \verb! 1 3 -1 [-3 5 3] 6 7 ! & -3 & 5 \\ \hline \verb! 1 3 -1 -3 [5 3 6] 7 ! & 3 & 6 \\ \hline \verb! 1 3 -1 -3 5 [3 6 7]! & 3 & 7 \\ \hline \end{array} 窗口位置[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,k
n,k。
第二行
n
n
n 个整数，表示序列
a
a
a
输出格式
输出共两行，第一行为每次窗口滑动的最小值
第二行为每次窗口滑动的最大值
样例 #1
样例输入 #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
%
50\%
50% 的数据，
1
≤
n
≤
1
0
5
1 \le n \le 10^5
1≤n≤105；
对于
100
%
100\%
100% 的数据，
1
≤
k
≤
n
≤
1
0
6
1\le k \le n \le 10^6
1≤k≤n≤106，
a
i
∈
[
−
2
31
,
2
31
)
a_i \in [-2^{31},2^{31})
ai∈[−231,231)。
AC代码：
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int>PII;
const int N=3e5+10;
const int MOD=9901;
const int INF=0X3F3F3F3F;
const int dx[]={-1,1,0,0,-1,-1,+1,+1};
const int dy[]={0,0,-1,1,-1,+1,-1,+1};
const int M = 1e6 + 10;
int n, k;
int q[M], a[M];
int main()
{
cin >> n >> k;
for(int i = 1; i <= n; i ++)
{
cin >> a[i];
}
//最小
int hh = 0, tt = -1;
for(int i = 1; i <= n; i ++)
{
if(hh <= tt && i - k >= q[hh]) hh ++;
while(hh <= tt && a[q[tt]] >= a[i]) tt --;
q[++ tt] = i;
if(i >= k) cout << a[q[hh]] << " ";
}
cout << endl;
hh = 0, tt = -1;
for(int i = 1; i <= n; i ++)
{
if(hh <= tt && i - k >= q[hh]) hh ++;
while(hh <= tt && a[q[tt]] <= a[i]) tt --;
q[++ tt] = i;
if(i >= k) cout << a[q[hh]] << " ";
}
cout << endl;
return 0;
}
原文地址：https://blog.csdn.net/2301_80882026/article/details/137608786
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！