Fractures @ 2019-08-16 20:27:20
萌新打了会单调队列的代码(滑动窗口求最小值),但是为什么输出结果不太一样呢
#include<cstdio>
#include<iomanip>
#include<queue>
const int MAXN=110000001;
using std::deque;
struct num{
int index,x;
};
int a[MAXN];
int n,m;
deque<num>q;
num t;
int main(){
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++){
scanf("%d",&a[i]);
}
for(int i=1;i<=n;i++){
t.index=i;
t.x=a[i];
if(q.empty()){
printf("0 ");
}
else{
if(q.front().index+m<i){
q.pop_front();
}
printf("%d ",q.front().x);
}
while((!q.empty())&&q.back().x>=a[i]){
q.pop_back();
}
q.push_back(t);
}
return 0;
}
输入:
8 3
1 3 -1 -3 5 3 6 7
应该输出:
-1 -3 -3 -3 3 3
实际输出:
0 1 1 -1 -3 -3 -3 3
by t162 @ 2019-08-16 20:29:14
显然
by t162 @ 2019-08-16 20:30:17
细节:窗口的大小必须为
by Cwling @ 2019-08-16 20:30:24
大佬您的码风以及单调队列的形式蒟蒻我欣赏不来
by muyang_233 @ 2019-08-16 20:46:03
窗口大小必须为k
by Fractures @ 2019-08-16 21:03:42
qaq