POJ2823 Sliding Window【双端队列】

2020-12-13 02:34

阅读：402

标签：双端队列

求连续的k个中最大最小值，k是滑动的，每次滑动一个

用双端队列维护可能的答案值

如果要求最小值，则维护一个单调递增的序列

对一开始的前k个，新加入的如果比队尾的小，则弹出队尾的，直到新加入的比队尾大，加入队尾

从第k+1个到最后一个，按照上述规则，压入新数，然后弹出队首元素（满足队首元素对应原来序列的位置必须在视窗内，否则，继续弹出下一个）

#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;

inline void put(int x){
    if(x=start;j--)//弹出比它大的数
//		{
//			if(q[j].v>num[i])
//				tail--;
//		}
		while(tail>=start&&q[tail].v>num[i])
            tail--;
		q[++tail].v=num[i];
		q[tail].p=i;//将该数加到尾巴
		//开始输出最小值
		if(i>=k)
		{
			while(i-q[start].p>k-1) start++;
			ansmin[pj++]=q[start].v;
		}
	}
	start=1;tail=1;
	for(int i=1;i=start;j--)//弹出比它小的数
//		{
//			if(q[j].v=start&&q[tail].v=k)
		{
			while(i-q[start].p>k-1) start++;
			ansmax[pjj++]=q[start].v;
		}
	}
	for(int i=0;i

 
POJ2823 Sliding Window【双端队列】,搜素材,soscw.com
POJ2823 Sliding Window【双端队列】
标签：双端队列
原文地址：http://blog.csdn.net/u011775691/article/details/28761461

上一篇：javacv 设置帧率（续）

下一篇：windows环境安装python虚拟环境

文章来自：搜素材网的编程语言模块，转载请注明文章出处。
文章标题：POJ2823 Sliding Window【双端队列】
文章链接：http://soscw.com/essay/25879.html

亲，登录后才可以留言！

POJ2823 Sliding Window【双端队列】

评论

热门文章

推荐文章

最新文章

置顶文章