关于双端队列 (单调队列板子题,滑动窗口)
  • 板块学术版
  • 楼主bloodstalk
  • 当前回复3
  • 已保存回复3
  • 发布时间2022/4/22 10:25
  • 上次更新2023/10/28 03:09:15
查看原帖
关于双端队列 (单调队列板子题,滑动窗口)
231543
bloodstalk楼主2022/4/22 10:25

代码如下,我想请问为什么当我样例输入-1的时候,我验证了一下对头元素,他还是1? 题目在这滑动窗口

#include<bits/stdc++.h>
#define int long long

using namespace std;

const int N=1e6+1;
int n,m;
struct node
{
	int h;
	int t;	
}a[N];
deque <node> dq; 

signed main()
{
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++)
	{
		scanf("%d",&a[i].h);
		a[i].t=i;
	}
	int tail=1,head=1;
	for(int i=1;i<=n;i++)
	{
		while(!dq.empty() && a[i].h<dq.back().h) dq.pop_back();
		dq.push_back(a[i]);
		cout<<dq.back().h<<" ";
		head=dq.front().t;
		tail=a[i].t;
		while(!dq.empty() && tail-head+1>m) dq.pop_front(),head=dq.front().t;
		//if(tail>=m) cout<<dq.front().h<<" ";
	}
	/*for(int i=1;i<=n;i++)
	{
		while(!dq.empty() && a[i].h<dq.back().h) dq.pop_back();
		dq.push_back(a[i]);
		cout<<dq.back().h<<" ";
		head=dq.front().t;
		tail=a[i].t;
		while(!dq.empty() && tail-head+1>m) dq.pop_front(),head=dq.front().t;
		//if(tail>=m) cout<<dq.front().h<<" ";
	}*/
	return 0;
}
2022/4/22 10:25
加载中...