@[GXZJQ](/user/1088732) 时间复杂度最高是 $k^2$，这就是 TLE 的原因
by heyx0201 @ 2024-01-03 13:20:53
@[GXZJQ](/user/1088732) 正解[单调队列](https://oi-wiki.org/ds/monotonous-queue/)
by heyx0201 @ 2024-01-03 13:22:59
@[heyx0201](/user/768951) 谢谢 ， 已过
by GXZJQ @ 2024-01-03 18:24:50
@[heyx0201](/user/768951) 逆天，这样能AC
```
#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 10;
int a[N], b[N], c[N];
int n, k, minn = 1e9, maxx = -1e9, cnt = 1;
int main() {
scanf("%d%d", &n, &k);
for (int i = 1; i <= n; i++)
scanf("%d", &a[i]);
for (int i = 1; i <= k; i++) {
minn = min(minn, a[i]);
maxx = max(maxx, a[i]);
}
b[1] = minn, c[1] = maxx;
int l = 1, r = k;
while (r <= n) {
if (a[l] == minn || a[l] == maxx) {
l++, r++, minn = 1e9, maxx = -1e9;
for (int i = l; i <= r; i++) {
minn = min(minn, a[i]);
maxx = max(maxx, a[i]);
}
} else {
l++, r++, minn = min(minn, a[r]), maxx = max(maxx, a[r]);
}
b[++cnt] = minn;
c[cnt] = maxx;
}
for (int i = 1; i < cnt; i++)
printf("%d ", b[i]);
printf("\n");
for (int i = 1; i < cnt; i++)
printf("%d ", c[i]);
return 0;
}
```
by kmlihaiming @ 2024-01-04 13:59:13
@[kmlihaiming](/user/920265) 什么算法/yiw
by heyx0201 @ 2024-01-04 21:38:57
@[heyx0201](/user/768951) 我也不清楚啊，就跟模拟很像，你可以看一下P3029这题，第一篇题解介绍了那个双指针two_pointer，跟尺取法很像，再加了一点优化就A了
by kmlihaiming @ 2024-01-05 13:25:22