作者：手机用户2502912857 | 来源：互联网 | 2023-05-17 20:53
此文为博主原创题解，转载时请通知博主，并把原文链接放在正文醒目位置。题目链接：https:www.luogu.orgproblemshow?pid1886题目描述现在有一堆数字共N个数字（N
此文为博主原创题解，转载时请通知博主，并把原文链接放在正文醒目位置。
题目链接：https://www.luogu.org/problem/show?pid=1886
题目描述
现在有一堆数字共N个数字（N<=10^6），以及一个大小为k的窗口。现在这个从左边开始向右滑动，每次滑动一个单位，求出每次滑动后窗口中的最大值和最小值。
输入输出格式
输入格式：
输入一共有两行，第一行为n,k。
第二行为n个数( 输出格式：
输出共两行，第一行为每次窗口滑动的最小值
第二行为每次窗口滑动的最大值
输入输出样例
输入样例#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%的数据，n<=10^5
100%的数据，n<=10^6
分析：
据说会单调队列的人一眼就能看出来这是个裸题！然而我不会
确实是个练单调队列的好题...不会的请自行百度，很容易理解，此博客不负责教学。
AC代码：
1 #include
2 #include
3 #include
4 #include
5
6 using namespace std;
7 const int MAXN = 1000005;
8
9 int n,k,note[MAXN],Min[MAXN],Max[MAXN],num[MAXN];
10
11 inline void read(int &x)
12 {
13 char ch = getchar(),c = ch;x = 0;
14 while(ch <'0' || ch > '9') c = ch,ch = getchar();
15 while(ch <= '9' && ch >= '0') x = (x<<1)+(x<<3)+ch-'0',ch = getchar();
16 if(c == '-') x = -x;
17 }
18
19 void find_Min()
20 {
21 int head = 1,tail = 0;
22 for(int i = 1;i i)
23 {
//放入新元素 24 while(head <= tail && num[i] <= Min[tail]) tail --
;
25 Min[++tail] =
num[i];
26 note[tail] =
i;
27 }
28 for(
int i = k;i <= n;++
i)
29 {
//进行滑动窗口 30 while(head <= tail && num[i] <= Min[tail]) tail --
;
31 Min[++tail] =
num[i];
32 note[tail] =
i;
33 while(note[head] <= i-k) head ++;
//排除最小值已经不在当前窗口内的情况 34 printf(
"%d ",Min[head]);
35 }
36 }
37 38 void find_Max()
39 {
//与min同理 40 int head =
1,tail =
0;
41 for(
int i =
1;i
i)
42 {
43 while(head <= tail && num[i] >= Max[tail]) tail --;
44 Max[++tail] = num[i];
45 note[tail] = i;
46 }
47 for(int i = k;i <= n;++ i)
48 {
49 while(head <= tail && num[i] >= Max[tail]) tail --;
50 Max[++tail] = num[i];
51 note[tail] = i;
52 while(note[head] <= i-k) head ++;
53 printf("%d ",Max[head]);
54 }
55 }
56
57 int main()
58 {
59 read(n),read(k);
60 for(int i = 1;i <= n;++ i)
61 read(num[i]);
62 find_Min();
63 puts("");
64 find_Max();
65 return 0;
66 }
京公网安备 11010802041100号