题目描述
blablabla
样例
blablabla
算法1
#include<iostream>
using namespace std;
const int N = 1e6 + 10;
int a[N];
int ma[N], mi[N];
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
int n,k;
int ha = 1, ta = 0, hi = 1, ti = 0;
cin >> n >> k;
mi[1] = 1, ma[1] = 1;
for (int i = 1; i <= n; i++) cin >> a[i];
for (int i = 1; i <= n; i++) {
if(mi[hi]<i-k+1)
hi++; //为何他一定要放后面 如果赋初值 mi[1] = 1 ,则可放在前面
//否则,mi[hi]第一次循环时一定是0,表达式一定成立,hi一定加1,总是比 i 快一步
while (ti >= hi && a[i] <= a[mi[ti]])
ti--;
mi[++ti] = i;
// printf("i=%d hi=%d ti=%d mi[hi]=%d mi[ti]=%d\n", i,hi,ti, mi[hi], mi[ti]);
if(i>=k) cout << a[mi[hi]] << " ";
}
cout << "\n";
for (int i = 1; i <= n; i++) {
if(ma[ha]<i-k+1) ha++;
while (ta >= ha && a[i] >= a[ma[ta]]) ta--;
ma[++ta] = i;
if(i>=k) cout << a[ma[ha]] << " ";
}
return 0;
}
算法2
#include<iostream>
using namespace std;
const int N = 1e6 + 10;
int a[N];
int ma[N], mi[N];
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
int n,k;
int ha = 1, ta = 0, hi = 1, ti = 0;
cin >> n >> k;
for (int i = 1; i <= n; i++) cin >> a[i];
for (int i = 1; i <= n; i++) {
while (ti >= hi && a[i] <= a[mi[ti]])
ti--;
mi[++ti] = i;
if(mi[hi]<i-k+1)
hi++; //为何他一定要放后面 如果赋初值 mi[1] = 1 ,则可放在前面
//否则,mi[hi]第一次循环时一定是0,表达式一定成立,hi一定加1,总是比 i 快一步
// printf("i=%d hi=%d ti=%d mi[hi]=%d mi[ti]=%d\n", i,hi,ti, mi[hi], mi[ti]);
if(i>=k) cout << a[mi[hi]] << " ";
}
cout << "\n";
for (int i = 1; i <= n; i++) {
while (ta >= ha && a[i] >= a[ma[ta]]) ta--;
ma[++ta] = i;
if(ma[ha]<i-k+1) ha++;
if(i>=k) cout << a[ma[ha]] << " ";
}
return 0;
}