POJ 2823 Sliding Window 【单调队列】

2020-12-13 05:07

阅读：332

题目链接：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

上一篇：创建spring boot的三种方式

下一篇：java二维数组

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

亲，登录后才可以留言！

POJ 2823 Sliding Window 【单调队列】

评论

热门文章

推荐文章

最新文章

置顶文章