@[zsenhe](/user/518293) 当然了，这题要用滑动窗口，不会的话可以用RMQ或者线段树
您的算法时间复杂度比较高，是O(nm)无法通过本题
by Xy_top @ 2022-11-07 20:43:34
@[stdios](/user/637796) 这是我尝试优化之后的代码，改进之后多AC了两个样例，还是有两个TLE，还有什么能优化的地方吗
```cpp
#include <iostream>
using namespace std;
const long long N = 1e7*3;
long long s[N];
long long q[N];
long long hh=0,tt=-1;
void handler(long long * s,int length,int k){
for(int i=0;i<length;i++){
if(i-k>q[hh]) hh++;
long long anser = 1e7*3;
while(hh<=tt&&s[i]<=s[q[tt]]) tt--;
cout << (i==0?0:s[q[hh]]) << endl;
q[++tt] = i;
}
}
int main(){
cin.tie(0);
int n,k;
cin>>n>>k;
for(int i=0;i<n;i++) cin>>s[i];
handler(s,n,k);
return 0;
}
```
by zsenhe @ 2022-11-07 20:57:18
@[zsenhe](/user/518293) 网络上搜单调队列
by simple_line @ 2022-11-07 21:09:06
@[simple_line](/user/538327)
我改成printf和scanf就过了，上面用的是单调队列
by zsenhe @ 2022-11-07 21:12:57
```cpp
#include <iostream>
using namespace std;
const int N = (1e7)*3;
int s[N],q[N],hh=0,tt=-1;
void handler(int * s,int length,int k){
for(int i=0;i<length;i++){
if(i-k>q[hh]) hh++;
while(hh<=tt&&s[i]<=s[q[tt]]) tt--;
printf("%d\n",i==0?0:s[q[hh]]);
q[++tt] = i;
}
}
int main(){
int n,k;
scanf("%d%d",&n,&k);
for(int i=0;i<n;i++) scanf("%d",&s[i]);
handler(s,n,k);
return 0;
}
```
ac的代码
by zsenhe @ 2022-11-07 21:14:02
@[zsenhe](/user/518293) cout其实不慢，在主函数里加上这一句话：
```cpp
ios::sync_with_srtdio(false);
```
cin cout比scanf printf还要快
但主要是cout的endl很慢很慢 所以不要用endl
如果想用cout输出换行，那么这样：
```cpp
cout << "\n";
```
速度也直接起飞
by Xy_top @ 2022-11-08 06:23:49
@[zsenhe](/user/518293) 您这个数组怎么开到$1e7\times $3？
看题目要求
by Xy_top @ 2022-11-08 06:24:55
@[stdios](/user/637796) 受教了
by zsenhe @ 2022-11-08 12:38:49
@[Xy_top](/user/637796) 果然是endl
by T17371361045 @ 2022-11-21 14:56:23
@[T17371361045](/user/793917) 这点小事儿就不要再@我了啦，我事情很多的啦！
by Xy_top @ 2022-11-21 18:17:19