fzjfzjfzj @ 2024-07-13 15:25:17
#include <bits/stdc++.h>
using namespace std;
deque<int> a;
int num[1000005],n,k,t;
int main()
{
cin>>n>>k;
a.clear();
for(int i=0;i<n;i++)
{
cin>>num[i];
}
t=0;
for(int i=0;i<n;i++)
{
while(!a.empty()&&a.back()>=num[i])
{
a.pop_back();
}
a.push_back(num[i]);
if(i-t>=k&&a.front()==num[t])
{
t++;
a.pop_front();
}
if(i-t>=k&&a.front()!=num[t])
{
t++;
}
if(i>=k-1)
{
cout<<a.front()<<" ";
}
}
cout<<endl;
a.clear();
t=0;
for(int i=0;i<n;i++)
{
while(!a.empty()&&a.back()<=num[i])
{
a.pop_back();
}
a.push_back(num[i]);
if(i-t>=k&&a.front()==num[t])
{
t++;
a.pop_front();
}
if(i-t>=k&&a.front()!=num[t])
{
t++;
}
if(i>=k-1)
{
cout<<a.front()<<" ";
}
}
return 0;
}by fzjfzjfzj @ 2024-07-13 15:46:54
@chenzhuoy thank you
by hzy_Q @ 2024-07-18 09:36:45
@fzjfzjfzj
#include<bits/stdc++.h>
using namespace std;
const int N=1e6+5;
int a[N];//记录原始信息
int main()
{
int n,k;
//单调性根据ai来决定
deque<int> dq;//dq记录原始信息ai下标i
scanf("%d%d",&n,&k);
//输入信息
for(int i=1;i<=n;i++) scanf("%d",a+i);
//利用单调队列求最小值(类似滑动窗口)
//dq.front()记录最小值 容器中元素单调上升
//过时的元素从front删除 不符合单调性的从back删除
for(int i=1;i<=n;i++)
{
//1.删除过时元素(下标i是一个个移动 只有一个过时)
if(!dq.empty()&&dq.front()+k<=i) dq.pop_front();
//2.删除不满足单调性的元素 有可能多个
while(!dq.empty()&&a[dq.back()]>=a[i]) dq.pop_back();
//3.将当前合格的元素放入容器
dq.push_back(i);//将下标装入
//4.输出答案 超过k长度才有输出
if(i>=k) printf("%d ",a[dq.front()]);//根据下标输出原始数据
}
printf("\n");//输出换行
dq.clear();//清空容器
//求最大值
for(int i=1;i<=n;i++)
{
//1.删除过时元素(下标i是一个个移动 只有一个过时)
if(!dq.empty()&&dq.front()+k<=i) dq.pop_front();
//2.删除不满足单调性的元素 有可能多个
while(!dq.empty()&&a[dq.back()]<=a[i]) dq.pop_back();
//3.将当前合格的元素放入容器
dq.push_back(i);//将下标装入
//4.输出答案 超过k长度才有输出
if(i>=k) printf("%d ",a[dq.front()]);//根据下标输出原始数据
}
return 0;
}
by fzjfzjfzj @ 2024-08-18 17:22:32
@hzy_Q thank you
by hzy_Q @ 2024-08-19 14:17:10
@fzjfzjfzj :)