精华内容
下载资源
问答
  • 单调队列算法
    2019-04-23 16:36:15

    单调队列算法笔记

    单调队列

    定义: 单调队列顾名思义,就是具有单调性质队列性质的数据结构,它可以从一边维护队列的单调性,也可以从两边维护队列的单调性(双端队列)。单调队列与单调栈(单调栈算法笔记)一样,只不过范围是在[l , r],单调栈做出来的题目单调队列也可以做。

    性质及用法

    1. 单调队列里面的元素具有单调性;
    2. 元素加入队列前会把队列破坏单调性的元素移除队列;
    3. 一般来说面对具有区间最优(最值)性质问题,并且具有两大性质,单调+队列的数据结构单调队列,可以使用单调队列,如题目1。
    4. 还有单调队列也是动态规划算法一个必备的优化手段

    算法步骤

    1. 对于一个数而言,它可以从队尾入队,必须满足题目的特定条件
    2. 对于一个队头的数而言,如果说新来的数,不仅是新来的具有潜力,而且又自身价值还比它价值高,那么不用说队头出
    3. 总而言之,队列的单调条件,性质如何设置,是我们解题的关键.

    例题

    1、239. Sliding Window Maximum

    这是一道经典的单调队列的题目,求滑动窗口的最大值;

    注意要维护队列两个方面:

    1. 队列的长度(不超过k);
    2. 队列中元素单调递减的;
    class Solution {
    public:
        vector<int> maxSlidingWindow(vector<int>& nums, int k) {
            vector<int> res;
            int n = nums.size();
            deque<int>dq;
            for(int i = 0; i < n; i++)
            {
                while(dq.size() && i - dq.front() >=k){//维护队列的长度不超过3,如果超过则弹出队首
                    dq.pop_front();
                }
                while(dq.size() && nums[i] >= nums[dq.back()]){//维护队列是单减的,如果当前大于队尾,将队尾移出, 直到队尾大于当前数组为止。
                    dq.pop_back();
                }
                dq.push_back(i);
                if(i >=k -1){//只有在i大于等于区间时才输出
                    res.push_back(nums[dq.front()]);
                }
            }
            return res;
        }
    };
    

    其他类似的题目

    1. 逛画览:为了看到更多名师的画花费最少的[l,r]
    2. 切蛋糕;从这N小块中找出连续的k块蛋糕(k≤M)(k≤M),使得其上的幸运值最大

    参考博客

    1. 秦淮岸单调队列讲义
    更多相关内容
  • 详解单调队列算法

    千次阅读 多人点赞 2021-03-17 00:24:21
    单调队列」在「数据结构」题中的分布较为广泛,且常被当作优化「动态规划」的一种重要手段,因此该算法在面试中考察的频率较高,属于必知必会的知识点。 队列 首先我们来回忆一下「队列」。「队列」是一种「先进先...

    前言 嘿!彩蛋!感觉有帮助就三连呗!

    如果你对这篇文章可感兴趣,可以点击「【访客必读 - 指引页】一文囊括主页内所有高质量博客」,查看完整博客分类与对应链接。

    在上一篇文章中,我们介绍了「单调栈」这一最常考察的线性数据结构。而今天我们将继续沿着这个思路,介绍另一个与其 “齐名” 的线性数据结构,即「单调队列」。

    「单调队列」在「数据结构」题中的分布较为广泛,且常被当作优化「动态规划」的一种重要手段,因此该算法在面试中考察的频率较高,属于必知必会的知识点。

    队列

    首先我们来回忆一下「队列」。「队列」是一种「先进先出」的线性数据结构,其中元素只能从队尾进,从队首出。

    如下图所示,3 1 4 5 2 7 依次入队又依次出队,其结果满足「先进先出」的要求。另外,有标记的位置分别代表队首与队尾,其中左边为队首。

    在这里插入图片描述

    单调队列

    回忆完「队列」后,我们开始「单调队列」的讲解。

    什么是「单调队列」?顾名思义,「单调队列」就是队列内元素满足单调性的队列结构。且为了满足队列内元素的单调性,队尾也可弹出元素。此处的单调性分为单调递增与单调递减,为了便于描述,接下来以「单调递增队列」为例进行讲解。

    「单调递增队

    展开全文
  • 单调队列 算法思想+模板

    题目背景

    给出一个长度为n的数组,编程输出每k个连续的数中的最大值和最小值。


    思路

    朴素暴力思路

    在这里插入图片描述

    单调队列优化

    要求的是每连续的k个数中的最小(最大)值,很明显,当一个数进入所要 “寻找” 最小值的范围中时,若这个数比其前面(先进队)的数要小,显然,前面的数会比这个数先出队且不再可能是最小值。
    也就是说——当满足以上条件时,可将前面的数 “弹出”,再将该数真正 push 进队尾。
    这就相当于维护了一个递增的队列,符合单调队列的定义,减少了重复的比较次数,不仅如此,由于维护出的队伍是查询范围内的且是递增的,队头必定是该查询区域内的最小值,因此输出时只需输出队头即可。
    显而易见的是,在这样的算法中,每个数只要进队与出队各一次,因此时间复杂度被降到了O(N)
    而由于查询区间长度是固定的,超出查询空间的值再小也不能输出,因此每次都需要判断一下对头元素是否已经不在滑动区间内了。


    代码模板

    #include<iostream>
    using namespace std;
    const int N=1000010;
    int a[N],q[N];      //注意,存在队列中的不是元素的值,而是元素的下标
    int hh=0,tt=-1;
    int main()
    {
        int n,k;
        scanf("%d%d",&n,&k);
        for(int i=0;i<n;i++) scanf("%d",&a[i]);
        
        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) printf("%d ",a[q[hh]]);   //至少得处理过k个元素才能输出第一个,因为确实是每k个元素找最值,没处理到k个的时候,不要输出
        }
        printf("\n");
        
        hh=0,tt=-1;
        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) printf("%d ",a[q[hh]]);
        }
        return 0;
    }
    

    注意点请参考注释


    主要应用

    • 滑动窗口(此题)
    • 动态规划时的状态优化
    展开全文
  • 单调队列常常用来维护固定数组中固定长度区间的最大最小值,通常使用双端队列实现。啥意思? 以这道模板题为例,讲述单调队列的用法。link 手造一组样例(与例题所给略有不同):(n=8,k=3n=8,k=3n=8,k=3) 1 3 -1 -...

    单调队列算法总结&专题训练

    一些 update

    update 2021/2/28:修改了『概述』部分。

    1.概述

    单调队列是一种特殊的队列,其保证队列内的元素单调递增。

    而单调队列通常解决的是这样一类问题:

    n n n 个数,给定长度 l e n len len,求所有区间 [ k , k + l e n ] ( k + l e n ≤ n , k ∈ [ 1 , n ] , k ∈ N ) [k,k+len](k+len \leq n,k \in [1,n],k \in N) [k,k+len](k+lenn,k[1,n],kN) 的最大最小值。

    确实这个可以用 st 表,线段树之类的做,但是带一个 log。

    而单调队列可以 O ( n ) O(n) O(n) 实现。

    2.模板

    以这道模板题为例,讲述单调队列的用法。link

    手造一组样例(与例题所给略有不同):( n = 8 , k = 3 n=8,k=3 n=8,k=3

    1 3 -1 -3 5 6 7 7

    以求最小值为例,建立一个双端队列。

    循环 i i i 从 1 到 n n n

    i = 1 i=1 i=1 时,队列为空,插入 a 1 a_1 a1

    队列: 1 ,最小值为 1 。

    i = 2 i=2 i=2 时, a 2 = 3 a_2=3 a2=3,比 队首元素 要大,难道我们就要残忍抛弃 a 2 a_2 a2 吗?

    不能! 虽然 a 2 > a 1 a_2 > a_1 a2>a1 ,但是随着时间的推移, a 1 a_1 a1首先被挤出队列,对后面不能做出贡献,但是 a 2 a_2 a2 活得更久 呆在队列里的时间更长,在 a 1 a_1 a1 离开之后就有可能成为答案,所以我们要将 a 2 a_2 a2 插入队列。(以上为单调队列一个重要思想)

    队列: 1 3,最小值为 1 。

    i = 3 i=3 i=3 时, a 3 = − 1 a_3=-1 a3=1,比前面的数都小,并且 a 3 a_3 a3呆在队列里的时间比 a 1 , a 2 a_1,a_2 a1,a2 更长,肯定比 a 1 , a 2 a_1,a_2 a1,a2 更优,那么要 a 1 , a 2 a_1,a_2 a1,a2有什么用?从队尾弹出 a 1 , a 2 a_1,a_2 a1,a2(这就是为什么要用双端队列而不是普通队列),插入 a 3 a_3 a3 。(以上为单调队列另一个重要思想)

    所以发现了吗?我们其实是要在队列里面维护一个单调递增序列。

    队列:-1,最小值为 -1。

    i = 4 i=4 i=4 时, a 4 > 队 尾 元 素 a_4>队尾元素 a4> ,根据 i = 3 i=3 i=3 的推论,弹出 a 3 a_3 a3 ,插入 a 4 a_4 a4

    队列:-3 ,最小值为 -3 。

    i = 5 i=5 i=5 时, a 5 > 队 尾 元 素 a_5>队尾元素 a5> ,根据 i = 2 i=2 i=2 的推论,插入 a 5 a_5 a5

    队列:-3 5

    i = 6 i=6 i=6 时, a 6 > 队 尾 元 素 a_6>队尾元素 a6> ,根据 i = 2 i=2 i=2 的推论,插入 a 6 a_6 a6

    队列:-3 5 6,最小值 -3。

    i = 7 i=7 i=7 时, a 7 > 队 尾 元 素 a_7>队尾元素 a7> ,根据 i = 2 i=2 i=2 的推论,插入 a 7 a_7 a7。。。。。。吗?

    要注意了!!!由于区间长度 k = 3 k=3 k=3 ,此时队首元素 a 4 = − 3 a_4=-3 a4=3 已经超出了区间长度的限制,无论有多小都不能对答案做出贡献,所以必须从队首弹出队列!

    所以弹出 a 4 a_4 a4 ,插入 a 7 a_7 a7

    队列:5 6 7,最小值为 5。

    最后 i = 8 i=8 i=8 时,首先弹出 a 4 a_4 a4 (过时了),然后??? a 8 = a 7 = 7 a_8=a_7=7 a8=a7=7 ,那么需不需要更新呢?

    需要!考虑到有区间长度的限制,所以 a 8 a_8 a8 必然比 a 7 a_7 a7 更优,因此需要从队尾弹出 a 7 a_7 a7 ,插入 a 8 a_8 a8

    队列:6 7,最小值为 6,不过此时的 7 代表 a 8 a_8 a8

    那么这样一来就有一个维护问题了,如何知道这个 7 代表 a 7 a_7 a7 还是 a 8 a_8 a8 呢?

    实际写代码时为了避免这个情况,我个人通常会使用数组下标存到队列里面,这样就没有这个问题了,后面的代码都是如此。

    理解如何使用单调队列求区间最小值后,求区间最大值就很轻松了,只需要仿照上述步骤,在队列内维护一个单调下降序列即可。

    模板的代码:

    #include<bits/stdc++.h>
    using namespace std;
    
    const int MAXN=1e6+10;
    int n,k,a[MAXN],ans[MAXN][2];
    deque<int>q;
    
    int read()
    {
    	int fh=1,sum=0;
    	char ch=getchar();
    	while(ch<'0'||ch>'9')
    	{
    		if(ch=='-') fh=-1;
    		ch=getchar();
    	}
    	while(ch>='0'&&ch<='9')
    	{
    		sum=(sum<<3)+(sum<<1)+ch-'0';
    		ch=getchar();
    	}
    	return sum*fh;
    }
    
    void GetMin()
    {
    	deque<int>q;
    	for(int i=1;i<=n;i++)
    	{
    		while(!q.empty()&&i-q.front()>=k) q.pop_front();
    		while(!q.empty()&&a[i]<=a[q.back()]) q.pop_back();
    		q.push_back(i);
    		if(i-k+1>0) ans[i-k+1][0]=a[q.front()];
    	}
    }
    
    void GetMax()
    {
    	deque<int>q;
    	for(int i=1;i<=n;i++)
    	{
    		while(!q.empty()&&i-q.front()>=k) q.pop_front();
    		while(!q.empty()&&a[i]>=a[q.back()]) q.pop_back();
    		q.push_back(i);
    		if(i-k+1>0) ans[i-k+1][1]=a[q.front()];
    	}
    }
    
    int main()
    {
    	n=read();k=read();
    	for(int i=1;i<=n;i++) a[i]=read();
    	GetMin();
    	GetMax();
    	for(int i=1;i<=n-k+1;i++) cout<<ans[i][0]<<" ";
    	cout<<"\n";
    	for(int i=1;i<=n-k+1;i++) cout<<ans[i][1]<<" ";
    	return 0;
    }
    

    如果你成功理解了上述代码,那么恭喜你,学会了单调队列!

    接下来是几道例题。

    3.例题

    例题1:luogu P1714

    暴力方法显而易见,那么我们如何使用单调队列解决此题呢?

    推敲题意可以发现:假如我们取出一个 n ∗ n n*n nn 的矩阵 a a a ,那么这个矩阵的最大值一定是每一列最大值的最大值,最小值一定是每一列的最小值的最小值。

    这就好做了!对每一列跑一次区间长度为 n n n 的单调队列,设 f [ i ] [ j ] [ 0 / 1 ] f[i][j][0/1] f[i][j][0/1] 表示第 j j j 列从第 i − k + 1 i-k+1 ik+1(如果小于 1 则从 1 开始) 行开始到第 i i i 行止的最大值/最小值,跑单调队列时存储答案,然后从第 n n n 行开始对每一行跑一次关于 f f f 的单调队列,计算最大值与最小值即可。更新答案时需要注意,只有 n ≤ j n \leq j nj 时才需要更新答案。

    代码:

    #include<bits/stdc++.h>
    using namespace std;
    
    const int MAXN=1000+10;
    int n,m,k,a[MAXN][MAXN],f[MAXN][MAXN][2],ans=0x7f7f7f7f;
    
    int read()
    {
    	int fh=1,sum=0;
    	char ch=getchar();
    	while(ch<'0'||ch>'9')
    	{
    		if(ch=='-') fh=-1;
    		ch=getchar();
    	}
    	while(ch>='0'&&ch<='9')
    	{
    		sum=(sum<<3)+(sum<<1)+ch-'0';
    		ch=getchar();
    	}
    	return sum*fh;
    }
    
    void lie()
    {
    	for(int j=1;j<=m;j++)
    	{
    		deque<int>qmax,qmin;
    		for(int i=1;i<=n;i++)
    		{
    			while(!qmax.empty()&&i-qmax.front()>=k) qmax.pop_front();
    			while(!qmin.empty()&&i-qmin.front()>=k) qmin.pop_front();
    			while(!qmax.empty()&&a[i][j]>=a[qmax.back()][j]) qmax.pop_back();
    			while(!qmin.empty()&&a[i][j]<=a[qmin.back()][j]) qmin.pop_back();
    			qmax.push_back(i),qmin.push_back(i);
    			f[i][j][0]=a[qmax.front()][j];
    			f[i][j][1]=a[qmin.front()][j];
    		}
    	}
    }//对每一列跑一次单调队列
    
    void hang()
    {
    	for(int i=k;i<=n;i++)
    	{
    		deque<int>qmax,qmin;
    		for(int j=1;j<=m;j++)
    		{
    			while(!qmax.empty()&&j-qmax.front()>=k) qmax.pop_front();
    			while(!qmin.empty()&&j-qmin.front()>=k) qmin.pop_front();
    			while(!qmax.empty()&&f[i][j][0]>=f[i][qmax.back()][0]) qmax.pop_back();
    			while(!qmin.empty()&&f[i][j][1]<=f[i][qmin.back()][1]) qmin.pop_back();
    			qmax.push_back(j),qmin.push_back(j);
    			if(j>=k) ans=min(ans,f[i][qmax.front()][0]-f[i][qmin.front()][1]);
    		}
    	}
    }//对每一行跑一次单调队列
    
    int main()
    {
    	n=read();m=read();k=read();
    	for(int i=1;i<=n;i++)
    		for(int j=1;j<=m;j++)
    			a[i][j]=read();
    	lie();
    	hang();
    	cout<<ans<<"\n";
    	return 0;
    }
    

    例题2:luogu P2698

    详见这篇博客

    例题3:烽火传递(Noip 2010 tg 初赛 完善程序 T2)

    题目大意:给定数列 a 1... n a_{1...n} a1...n,从中选出若干个数使得连续 m m m 个数内至少有一个数被选中,求被选中的数和的最小值。

    输入格式:

    第一行 n , m n,m n,m ,第 2 行 n n n 个数表示 a 1... n a_{1...n} a1...n

    范围: 1 ≤ m ≤ n ≤ 1 0 5 , 1 ≤ a i ≤ 100 1 \leq m \leq n \leq 10^5,1 \leq a_i \leq 100 1mn105,1ai100

    输出格式:

    求被选中的数和的最小值。

    样例:

    input:
    5 3
    1 2 5 6 2
    output:
    4
    

    题解:

    其实我并不是太懂出题人给的程序。。。所以怎么用单调队列呢?

    这一道题有最小二字,结合数据范围,可以推断出这道题是一道 dp 题。(说贪心的请自行靠边站)

    首先设状态:设 f i f_i fi 表示取第 i i i 个数后前 i i i 个数取数的最小值。

    然后推方程: f i = min ⁡ ( f j ) + a i , j ∈ [ i − m , i − 1 ] f_i=\min(f_j)+a_i,j \in [i-m,i-1] fi=min(fj)+ai,j[im,i1] ,应该不难想吧。

    所以如何使用单调队列呢?观察到 min ⁡ ( f j ) , j ∈ [ i − m , i − 1 ] \min(f_j),j \in [i-m,i-1] min(fj),j[im,i1],显然是固定长度 m m m ,可以使用单调队列维护。

    这是一道经典的单调队列优化 dp 的题目,放代码:

    #include<bits/stdc++.h>
    using namespace std;
    
    const int MAXN=1e5+10;
    int n,m,f[MAXN],a[MAXN],ans;
    deque<int>q;
    
    int read()
    {
    	int fh=1,sum=0;
    	char ch=getchar();
    	while(ch<'0'||ch>'9')
    	{
    		if(ch=='-') fh=-1;
    		ch=getchar();
    	}
    	while(ch>='0'&&ch<='9')
    	{
    		sum=(sum<<3)+(sum<<1)+ch-'0';
    		ch=getchar();
    	}
    	return sum*fh;
    }
    
    int main()
    {
    	n=read();m=read();ans=0x7f7f7f7f;
    	for(int i=1;i<=n;i++) a[i]=read();
    	q.push_back(0);//记得把0推入队列,原因请自行思考
    	for(int i=1;i<=n;i++)
    	{
    		while(!q.empty()&&i-q.front()>m) q.pop_front();
    		f[i]=f[q.front()]+a[i];
    		while(!q.empty()&&f[q.back()]>=f[i]) q.pop_back();
    		q.push_back(i);
    	}
    	for(int i=n;i>=n-m+1;i--) ans=min(ans,f[i]);
    	cout<<ans<<"\n";
    	return 0;
    }
    

    例题4:CF372C

    详见这篇博客

    4.总结

    相信在做完上述题目后,各位对单调队列有了一定程度的了解。单调队列可以用来维护一个序列上固定长度区间的最大最小值,可以与各种算法如 dp 相结合。

    展开全文
  • - 单调栈:求出某个数的左边或右边第一个比它大或小的元素。 - 单调队列:区间最大值最小值问题。
  • 输入 数组长度和滑动区间长度 8 3 数组 1 3 -1 -3 5 3 6 7 输出 分别为区间最小和区间最大 -1 -3 -3 -3 3 3 3 3 5 5 6 7 public class 单调队列_滑动窗口 { //初始化,为10的六次方的数据量,a为输入的数值存储,q...
  • 滑动窗口 单调队列算法解释及应用滑动窗口算法详解动画演示例题分析代码模板单调队列算法详解动画演示例题分析代码模板 滑动窗口 滑动窗口 可以用于处理一个数组或字符串的子区间问题 算法详解 动画演示 例题分析 ...
  • 题目大意: 给定一个长度为N的序列,请你求出它最大长度不超过M的...所以我们可以通过队列来优化 (这个算法我们称之为单调队列算法) 我们先枚举子序列的有端点 i 此时问题转变为寻找一个 j 最为子序列的左端点...
  • 单调队列模板+例题

    2020-10-03 10:34:55
    刷题模板,直接按套路码!!!!!单调队列是指:队列中元素之间的关系具有单调性,而且,队首和队尾都可以进行出队操作,只有队尾可以进行入队操作。
  • 算法单调队列

    千次阅读 2022-06-08 15:56:38
    单调队列

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 18,136
精华内容 7,254
关键字:

单调队列算法