题目描述
现在有一堆数字共N个数字（N<=10^6），以及一个大小为k的窗口。现在这个从左边开始向右滑动，每次滑动一个单位，求出每次滑动后窗口中的最大值和最小值。
例如：
The array is [1 3 -1 -3 5 3 6 7], and k = 3.
| 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 |
输入格式
输入一共有两行，第一行为n,k。
第二行为n个数(<INT_MAX)。
输出格式
输出共两行，第一行为每次窗口滑动的最小值
第二行为每次窗口滑动的最大值
输入样例
8 3
1 3 -1 -3 5 3 6 7
输出样例
-1 -3 -3 -3 3 3
3 3 5 5 6 7
说明
50%的数据，n<=10^5
100%的数据，n<=10^6
Solution
这道RMQ题可用单调队列做，如果用树状数组和线段树会被卡掉，所以单调队列是这道题的不二选择。
基本上单调队列模板连变都不用变，但是我特判了一个点。
Code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
| #include<cstdio>
#include<iostream>
#include<cstring>
using namespace std;
int a[1000001],q[1000001],p[1000001];
void init(){
memset(p,0,sizeof(p));
memset(q,0,sizeof(q));
}
void maxq(int g[],int len,int le) {
init();
int h=1,t=0,l=0;
for (int i=1; i<=len; i++) {
while (i-p[h]>=le&&(h<t)) h++;
while (t>=h&&t>0&&t>=l&&q[t]<a[i]) t--;
t++;
q[t]=a[i];
p[t]=i;
if (i>=le) cout<<q[h]<<' ';
}
}
void minq(int g[],int len,int le) {
int h=1,t=0,l=0;
init();
for (int i=1; i<=len; i++) {
while (i-p[h]>=le&&(h<t)) h++;
while (t>=h&&t>0&&t>=l&&q[t]>a[i]) t--;
t++;
q[t]=a[i];
p[t]=i;
if (i>=le) cout<<q[h]<<' ';
}
}
int main() {
int n,k;
cin>>n>>k;
for (int i=1; i<=n; i++) cin>>a[i];
if(k==1){
for (int i=1; i<=n; i++) cout<<a[i]<<" ";
cout<<"\n";
for (int i=1; i<=n; i++) cout<<a[i]<<" ";
return 0;
}
minq(a,n,k);
cout<<"\n";
maxq(a,n,k);
}
|
