双端单调队列

左手的ㄟ右手 2022-05-12 08:06 165阅读 0赞

上次我们介绍了单调栈结构[https://blog.csdn.net/hebtu666/article/details/82717317][https_blog.csdn.net_hebtu666_article_details_82717317]

这次介绍一种新的数据结构：双端队列：双端队列是指允许两端都可以进行入队和出队操作的队列，其元素的逻辑结构仍是线性结构。将队列的两端分别称为前端和后端，两端都可以入队和出队。

堆栈、队列和优先队列都可以采用双端队列来实现

本文介绍单调双端队列的原理及应用。

单调队列，顾名思义，就是一个元素单调的队列，那么就能保证队首的元素是最小（最大）的，从而满足最优性问题的需求。

给定一个长度为n的数列，一个k，求所有的min(ai,ai+1.....ai+k-1),i=0,1,....n-k

通俗一点说就是一个长度固定的滑动的窗口，求每个窗口内的最小值。

你当然可以暴力求解，依次遍历每个窗口.

介绍单调队列用法：我们维护一个单调队列

单调队列呢，以单调递增序列为例：

1、如果队列的长度一定，先判断队首元素是否在规定范围内，如果超范围则增长队首。

2、每次加入元素时和队尾比较，如果当前元素小于队尾且队列非空，则减小尾指针，队尾元素依次出队，直到满足队列的调性为止

我们说算法的优化就是重复计算过程的去除。

按窗口一次次遍历就是重复计算。最值信息没有利用好。

我们为什么可以这么维护？

首先，遍历到的元素肯定在队列元素之后。

其次，如果当前元素更小的话。

头部的值比当前元素大，头部还比当前元素先过期。所以以后计算再也不会用到它了。我们可以放心的去掉它。

下面给出代码和解释

int n,k;//长度为n的数列，窗口为k
    int a[MAX_N];//数列
    int b[MAX_N];//存放
    int deq[MAX_N]//模拟队列
    
    void solve()
    {
        int s = 0,t = 0;//头和尾
        for(int i=0;i<n;i++)
        {
            //不满足单调,尾就弹出
            while(s<t && a[deq[t-1]]>=a[i])t--;
            //直到满足，放入
            deq[t++]=i;
            //计算窗口最大值
            if(i-k+1>=0)b[i-k+1]=a[deq[s];
            //判断头过期弹出
            if(deq[s]==i-k+1)s++;
        }
    }

基本入门就到这里。

[https_blog.csdn.net_hebtu666_article_details_82717317]: https://blog.csdn.net/hebtu666/article/details/82717317