题目描述
blablabla
样例
#include <iostream>
#include <cstring>
#include <deque>
using namespace std;
const int N=1e6+10;
int n,k,a[N];//数组a用来存放所有的
int main(){
cin.tie(0);
cin>>n>>k;
for (int i=1;i<=n;i++){
scanf("%d",&a[i]);
}//输入数组元素
deque <int> q;
//q.push_back(a[1]);
for(int i=1;i<=n;i++){//找最小值
while(!q.empty()&&q.back()>a[i]){
q.pop_back();//新进来的元素如果更小的话,就把队尾的丢了
}
q.push_back(a[i]);//压入新元素
if(i-k>=1&&q.front()==a[i-k]){
q.pop_front();//判断对头是否滑出滑动窗口
}
if(i>=k) cout<<q.front()<<' ';
}
q.clear();//清空队列
cout<<endl;
for(int i=1;i<=n;i++){//找最大值
while(!q.empty()&&q.back()<a[i]){
q.pop_back();
}
q.push_back(a[i]);
if(i-k>=1&&q.front()==a[i-k]){
q.pop_front();
}
if(i>=k) cout<<q.front()<<' ';
}
}
算法1
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
blablabla
算法2
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
blablabla