17.单调队列

• 模拟队列

原题链接

#include <iostream>

using namespace std;

const int N=1e5+10;

int n;
int tt=0,hh=0;
int q[N];

int main()
{
    cin>>n;
    while(n--)
    {
        string s;
        cin>>s;
        //->hh.......tt
        if(s=="push")
        {
            int x;
            cin>>x;
            q[tt++]=x;
        }
        else if(s=="pop")
        {
            hh++;
        }
        else if(s=="empty")
        {
            if(hh<tt)
                cout<<"NO"<<endl;
            else
                cout<<"YES"<<endl;
        }
        else if(s=="query")//查询队头元素。
        {
            cout<<q[hh]<<endl;
        }
        
    }
    return 0;
}

• 单调队列

原题链接

• 递增队列

int hh=0,tt=0;
    for(int i=0;i<n;i++)
    {
        //判断队头是否已经出窗口,每次滑动一个单位
        if(hh<=tt&&i-k+1>q[hh]) 
            hh++;
        while(hh<=tt&&a[q[tt]]>=a[i])
            tt--;//出队
        q[++tt]=i;//把当前这个数插到队列里面去，该句先
        if(i-k+1>=0) //滑动窗口满了
            printf("%d ",a[q[hh]]);
    }

• 递减队列

    hh=0,tt=0;
    for(int i=0;i<n;i++)
    {
        if(hh<=tt&&que[hh]<i-k+1)
            hh++;
        while(hh<=tt&&a[que[tt]]<=a[i])
            tt--;
        que[++tt]=i;
        if(i>=k-1)
            printf("%d ",a[que[hh]]);
    }
}