POJ 2823 Sliding Window 【单调队列】

2020-12-13 03:13

阅读：277

标签：acm c++ poj 数据结构队列

题目链接：http://poj.org/problem?id=2823

题目大意：给出一组数，一个固定大小的窗口在这个数组上滑动，要求出每次滑动该窗口内的最大值和最小值。

这就是典型的单调队列，单调队列的作用就在此。单调队列的队首为区间内的最值，但是整个队列不用保持单调。

用两个队列分别处理最大值和最小值，在此说明一下最大值；

往队列中添加值num时，从队尾开始扫，直到遇到一个小于num的d值，将num插入d的后一位。之后的元素全部无效化（不管后面的元素就行）。查找最大值的时候，从队首开始找，如果该元素没在此时的区间的话，查找下一个，直到找到满足条件的第一个元素，这个元素便是最值。

求最小值和最大值大同小异，只需要将添加值num的条件改一下即可。

代码如下：

#include 
#include 
#define N 1000001
using namespace std;

struct que
{
    int i,x;
}q1[N],q2[N];//队列
int a[N];//输入数据
int n,k；
int head,tail;//分别代表队首和队尾的下标，head之前和tail之后的元素都无效
void getmax()
{
    head=1;tail=0;
    for(int i=0;i
        q1[tail].x=a[i];
        q1[tail].i=i;
        if(i>=k-1)
        {
            while(q1[head].ia[i])
            tail--;
        tail++;
        q2[tail].x=a[i];
        q2[tail].i=i;
        if(i>=k-1)
        {
            while(q2[head].i




POJ 2823 Sliding Window  【单调队列】,搜素材,soscw.com
POJ 2823 Sliding Window  【单调队列】
标签：acm   c++   poj   数据结构   队列   
原文地址：http://blog.csdn.net/u013912596/article/details/32710319

上一篇：在win7下安装VC6.0

下一篇：JavaWeb实现用户登录注册功能实例代码(基于Servlet+JSP+JavaBean模式)

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

亲，登录后才可以留言！

POJ 2823 Sliding Window 【单调队列】

评论

热门文章

推荐文章

最新文章

置顶文章