qwerzxjj @ 2022-07-14 16:30:02
#include <bits/stdc++.h>
using namespace std;
int m,n;
int a[1000001];//用于储存输入序列
deque <int> p,q;
void da()//求最大值，最小值同理
{
p.push_back(a[1]);
for(int i = 2;i <= n;i++)
{
while(a[i] >= p.front() && !p.empty())
{
p.pop_front();
}
p.push_back(a[i]);
}//求出第一个窗口里的最大值并构建其单调队列
cout << p.front() << " ";
for(int i = 1;i <= m - n;i++)
{
if(a[i] == p.front())//滑出窗口的是最大值，队首出队
{
p.pop_front();
}
while(a[n+i] >= p.back() && !p.empty())//为保证单调性，只在队尾大于新进入值时让新进入值入队
{
p.pop_back();
}
p.push_back(a[n+i]);
cout << p.front() << " ";
}
}
void xiao()
{
q.push_back(a[1]);
for(int i = 2;i <= n;i++)
{
while(a[i] <= q.front() && !q.empty())
{
q.pop_front();
}
q.push_back(a[i]);
}
cout << q.front() << " ";
for(int i = 1;i <= m - n;i++)
{
if(a[i] == q.front())
{
q.pop_front();
}
while(a[n+i] <= q.back() && !q.empty())
{
q.pop_back();
}
q.push_back(a[n+i]);
cout << q.front() << " ";
}
cout << endl;
}
int main()
{
cin >> m >> n;
for(int i = 1;i <= m;i++)
{
cin >> a[i];
}
xiao();
da();
return 0;
}by manyc @ 2023-04-02 22:10:04
@qwerzxjj 你队列好像有点问题，我也没细看，我的ACcode:
#include<bits/stdc++.h>
using namespace std;
const int N=1e6+5;
int a[N],n,k;
deque<int> p;
deque<int> q;
int main(){
cin>>n>>k;
for(int i=1;i<=n;i++) cin>>a[i];
for(int i=1;i<=n;i++){
while(p.size()&&i-p.front()+1>k) p.pop_front();
while(p.size()&&a[p.back()]>=a[i]) p.pop_back();
p.push_back(i);
if(i>=k) cout<<a[p.front()]<<" ";
}
cout<<endl;
for(int i=1;i<=n;i++){
while(q.size()&&i-q.front()+1>k) q.pop_front();
while(q.size()&&a[q.back()]<=a[i]) q.pop_back();
q.push_back(i);
if(i>=k) cout<<a[q.front()]<<" ";
}
return 0;
}