单调队列 订阅
单调队列,即单调递减或单调递增的队列。使用频率不高,但在有些程序中会有非同寻常的作用。 展开全文
单调队列,即单调递减或单调递增的队列。使用频率不高,但在有些程序中会有非同寻常的作用。
信息
外文名
Monotone queue
属    于
优先队列的一种
基本方程
f[x]=max/min{g(k)}+w[x]
地    位
使用频率不高,但偶尔有重要作用
作    用
1D/1D动态规划等
中文名
单调队列
范    围
限制较多
基于此的算法
基础上改进的斜率优化,单调栈等
代码长度
较短,容易调试
OI/ACM重要性
各种神奇算法的基础
单调队列单调队列的操作
不妨用一个问题来说明单调队列的作用和操作:不断地向缓存数组里读入元素,也不时地去掉最老的元素,不定期的询问当前缓存数组里的最小的元素。最直接的方法:普通队列实现缓存数组。进队出队都是O(1),一次查询需要遍历当前队列的所有元素,故O(n)。堆顶始终是最小元素,故查询是O(1)。而进队出队,都要调整堆,是O(log(n))。RMQ即Range Maximum(Minimum) Query,用来求某个区间内的最大值或最小值。使用线段树或稀疏表是O(log(n))级的。对于这类问题这两种方法也搞得定,但是没有单调队列快。由于单调队列的队头每次一定最小值,故查询为O(1)。进队出队稍微复杂点:进队时,将进队的元素为e,从队尾往前扫描,直到找到一个不大于e的元素d,将e放在d之后,舍弃e之后的所有元素;如果没有找到这样一个d,则将e放在队头(此时队列里只有这一个元素)。出队时,将出队的元素为e,从队头向后扫描,直到找到一个元素f比e后进队,舍弃f之前所有的。(实际操作中,由于是按序逐个出队,所以每次只需要出队只需要比较队头)。每个元素最多进队一次,出队一次,摊排分析下来仍然是 O(1)。上面的话可能还是没能讲出单调队列的核心:队列并不实际存在的,实际存在的是具有单调性的子序列。对这个子序列按心中的队列进行操作,譬如在进队时丢弃的元素,虽然它不存在于这个子序列里,但是还是认为他存在于队列里。另外,进队的顺序和出队的顺序并不一定相同,因为这个队列本身是隐含存在的,可以在进队时看成一个队列,出队时看成另一个队列,只要出队的元素在队列中就行。可以想象成一个队列只有头和身,另一个队列只有身和尾,而这身是共用的。在OI赛场上,大多数题目为单调队列力所不能及的,取而代之的是单调队列基础上改进的斜率优化,单调栈等,因为其限制条件,故潜力不大。但需要掌握,因为有许多算法建立在其基础上。例如斜率优化即为f[i] = min/max{f[j] + g[i] * g[j]},和单调队列尤为相似。单调栈即为单调队列的“栈”版。这两种复杂度也是O(n)的。
收起全文
精华内容
下载资源
问答
  • 单调队列
    多人点赞 热门讨论
    2021-09-11 23:43:38
    • 博客主页: https://blog.csdn.net/qq_50285142
    • 欢迎点赞👍收藏✨关注❤留言 📝 如有错误,敬请指正
    • 🎈虽然生活很难,但我们也要一直走下去🎈

    点击👉STL详解👈了解更多队列知识

    单调队列

    1.初步认识

    单调队列是一个数据结构,并不是STL里面的内容。

    单调队列为何说单调,因为是队列中的元素始终保持着单增或者单减的特性。(注意始终保持这四个字

    简单的sort排序就可以让一个序列有序了,为何又多此一举多出来个单调队列实现类似的功能呢?

    其实单调队列不只是做到了排序,还可以实现一个功能:在每次加入或者删除元素时都保持序列里的元素有序,即队首元素始终是最小值或者最大值,这个功能非常重要,单调队列我们就是使用的这个功能。

    举个例子:我们依次加入5个元素,分别为5,8,2,4,1
    那么我们假设队列是单减的,那么队首元素始终是最大的,五次操作后的队列元素排列情况如下:

    1: 5
    2: 8
    3: 8 2
    4: 8 4
    5: 8 4 1
    

    详细过程如下:

    1.首先队列里面没有元素,5加进去。
    2.第二个元素8大于队尾的元素,所以5要弹出去,8加进去。保持队首最大
    3.第三个元素2小于队尾元素8,可以加进去,变为8 2
    4.4大于队尾元素2,2弹出,4小于8,8不弹出,4加进去
    5.1小于队尾元素4,1加进去,最后队列为8 4 1

    2.实现

    单调队列我们使用数组进行模拟,下面是求每个长度为2的区间的最小值

    首先设置队首和队尾指向的下标。
    注意:队首指向0,队尾指向-1,默认的是队列里面没有元素

    然后就是对队列的操作:

    1.检查队首:如果队首指向的下标小于等于i-k,即队首的元素已经跑出了k长度即 [ i − k + 1 , i ] [i-k+1,i] [ik+1,i]这个区间,那么就要将队首元素弹出来,对应将hh加一

    2.检查队尾:如果队尾的元素大于要添加的值,如果这个值加上去队列就不会保持单调性,所以要弹出队尾元素,对应tt减一(可能会一直不满足,所以要一直(所以要while)弹出队尾元素)。目的就是保持队首元素一直是最小值,且队列单调

    3.加入队尾元素: q [ + + t t ] = i q[++tt] = i q[++tt]=i,首先tt加一要腾出位置,加入的是元素的下标,一定注意。

    #include<bits/stdc++.h>
    using namespace std;
    const int N = 1e5+5;
    
    int a[N],q[N];
    int n,k;
    
    int main()
    {
    	cin>>n>>k;
    	int hh = 0,tt = -1;
    	for(int i=1;i<=n;i++)
    	{
    		cin>>a[i];
    		//要插入元素了
    		while(hh <= tt and i - k >= q[hh]) hh++; //先把不满足的搞出去
    		while(hh <= tt and a[q[tt]] >= a[i]) tt--; // 然后为插入元素制造条件
    		q[++tt] = i; //插入操作
    		if(i>=k) cout<<a[q[hh]]<<" ";//i大于等于k,说明区间长度已经大于等于k,可以输出了
    	}
    	cout<<endl;
    	return  0;
     } 
    

    输入数据:

    5 2
    3 4 1 6 2
    

    结果:

    3 1 1 2
    

    3.基本应用–滑动窗口问题

    实现在固定长度区间的最大最小值问题的求解

    👉题目链接👈
    在这里插入图片描述

    #include<bits/stdc++.h>
    using namespace std;
    const int N = 1e6+5;
    
    int a[N],q[N];
    int n,k;
    
    int main()
    {
        cin>>n>>k;
        for(int i=1;i<=n;i++) cin>>a[i];
        
        int hh = 0,tt = -1 ;
        for(int i=1;i<=n;i++)
        {
            while(hh<=tt and i-k>=q[hh]) hh++;//处理队首
            while(hh<=tt and a[q[tt]] >= a[i]) tt--;//处理队尾
            q[++tt] = i;//队尾元素加入
            if(i>=k) cout<<a[q[hh]]<<" ";//输出队首元素
        }
        cout<<endl;
        //重新进行相反单调性的操作
        hh = 0,tt = -1;
        for(int i=1;i<=n;i++)
        {
            while(hh<=tt and i-k>=q[hh]) hh++;
            while(hh<=tt and a[q[tt]] <= a[i]) tt--;
            q[++tt] = i;
            if(i>=k) cout<<a[q[hh]]<<" ";
        }
        cout<<endl;
        return 0;
    }
    

    进阶–单调队列优化DP

    题目:Golden Sword

    https://www.luogu.com.cn/problem/P5858


    直接给转移方程:

    f [ i ] [ j ] = m a x ( f [ i − 1 ] [ k ] + a [ i ] ∗ j ) , j − 1 ≤ k ≤ m i n ( j + s − 1 , w ) f[i][j] = max(f[i - 1][k]+a[i] * j), j - 1 \leq k \leq min(j + s -1,w ) f[i][j]=max(f[i1][k]+a[i]j),j1kmin(j+s1,w)

    本来正常转移的话:
    第一层循环为对i的循环
    第二层循环为对j的循环,目的是为了更新每个 f [ i ] [ j ] f[i][j] f[i][j]
    因为有最大值操作,是对区间 [ j − 1 , m i n ( j + s − 1 , w ) ] [j-1, min(j+s-1,w)] [j1,min(j+s1,w)]求最大值,所以就要再进行一次循环求最大值(见下文代码)
    所以共三层循环,复杂度太大,需要进行优化。

    以下是对max的优化

    优化限定区间长度max值操作考虑单调队列

    q[]中存储的是最大值的下标,用f[i-1][hh]得到最大值

    维护限定区间最大值为什么从右向左转移?
    因为区间要求是 [ j − 1 , m i n ( j + s − 1 , w ) ] [j-1, min(j+s-1,w)] [j1,min(j+s1,w)],左端点看起来就比较固定,右端点用了min操作,就不那么固定了。

    如何求出i - 1(前一个状态)的区间最大值呢?考虑先把w加进单调队列,因为是从右往左操作,然后每次就直接加j - 1 到单调队列中(第一次的时候w就不会加进去,所以要首先把w加进去),可以保证每次加的j - 1是最新的(也可以说是区间左端点),但是最早加进单调队列的下标可能就不满足条件,需要判断。

    正常转移方程的代码:

    #include<bits/stdc++.h>
    using namespace std;
    
    using ll = long long ;
    using pii = pair<int, int>;
    const int N = 5005, mod = 998244353;
    
    int n, w, s;
    int a[N];
    ll f[N][N];
    
    void solve()
    {
    	cin >> n >> w >> s;
    	for(int i = 1; i <= n; i++)
    		cin >> a[i];
    
    	for(int i = 0; i <= n; i++)
    		for(int j = 0; j <= w; j++)
    			f[i][j] = -1e18;
    
    	f[0][0] = 0;
    	for(int i = 1; i <= n; i++)
    		for(int j = 1; j <= w; j++)
    			for(int k = j - 1; k <= min(j + s - 1, w); k++)
    				f[i][j] = max(f[i][j], f[i - 1][k] + 1ll * j * a[i]);
    
    	ll res = -1e18;
    	for(int i = 0; i <= w; i++)
    		res = max(res, f[n][i]);
    
    	cout << res << "\n";
    }
    
    int main()
    {
    	ios::sync_with_stdio(false);
    	cin.tie(0);
    
    	int t;
    	// cin >> t;
    	t = 1;
    	while(t--)
    		solve();
    	return 0;
    }
    

    单调队列优化之后的代码:

    #include<bits/stdc++.h>
    using namespace std;
    
    using ll = long long ;
    using pii = pair<int, int>;
    const int N = 5005, mod = 998244353;
    
    int n, w, s;
    int a[N];
    ll f[N][N], q[N];
    
    void solve()
    {
    	cin >> n >> w >> s;
    	for(int i = 1; i <= n; i++)
    		cin >> a[i];
    
    	for(int i = 0; i <= n; i++)
    		for(int j = 0; j <= w; j++)
    			f[i][j] = -1e18;
    
    	f[0][0] = 0;
    	for(int i = 1; i <= n; i++)
    	{
    		int hh = 0, tt = -1;
    		q[++tt] = w;//先加w,之后每次操作加 j - 1
    		for(int j = w; j >= 1; j--)
    		{
    			while(hh <= tt and q[hh] > min(j + s - 1, w)) ++hh;
    			while(hh <= tt and f[i - 1][q[tt]] < f[i - 1][j - 1]) --tt;
    			q[++tt] = j - 1;
    			// 加完之后 就可以得到最大值了
    			f[i][j] = f[i - 1][q[hh]] + 1ll * j * a[i];
    		}
    	}
    	
    	ll res = -1e18;
    	for(int i = 0; i <= w; i++)
    		res = max(res, f[n][i]);
    
    	cout << res << "\n";
    }
    
    int main()
    {
    	ios::sync_with_stdio(false);
    	cin.tie(0);
    
    	int t;
    	// cin >> t;
    	t = 1;
    	while(t--)
    		solve();
    	return 0;
    }
    

    例题

    理想的正方形

    https://blog.csdn.net/qq_50285142/article/details/119487336

    修建草坪

    https://blog.csdn.net/qq_50285142/article/details/119482927

    绿色通道

    https://blog.csdn.net/qq_50285142/article/details/119464406

    烽火传递

    https://blog.csdn.net/qq_50285142/article/details/119460222

    更多相关内容
  •  单调队列,就是一个符合单调性质的队列,它同时具有单调的性质以及队列的性质。他在编程中使用频率不高,但却占有至关重要的地位。它的作用很简单,就是为了维护一组单调数据,让我们在运行的过程中能够快速寻求前...
  • 寻找窗口的最大值最小值,是一个局部的概念,可以使用单调队列。 如最小值(从队首到队尾单增):先装上前k-1个,如果队列不为空且要加入的元素值小于队列尾的值,则将队尾弹出,直到队尾小于要加入的元素或者队列为...
  • 单调队列

    多人点赞 2021-04-21 19:12:17
    文章目录前言一、单调队列1.单调队列2.AcWing 154. 滑动窗口题目分析:AC代码二、时间复杂度 前言 复习acwing算法基础课的内容,本篇为讲解基础算法:单调队列,关于时间复杂度:目前博主不太会计算,先鸽了,日后...


    前言

    复习acwing算法基础课的内容,本篇为讲解基础算法:单调队列,关于时间复杂度:目前博主不太会计算,先鸽了,日后一定补上。


    一、单调队列

    1.单调队列

    同单调栈一样,在单调队列的元素中,同样也是按照从大到小或是从小到大的顺序进行排列的,有关单调栈,详见博客:单调栈,本博客关于单调队列是用数组模拟队列,如何用数组模拟队列见博客用数组模拟队列,这里不做赘述,关于单调队列的应用和作用,我们由一道题目展开.

    2.AcWing 154. 滑动窗口

    本题链接:滑动窗口
    本博客给出题目截图:

    在这里插入图片描述
    在这里插入图片描述

    题目分析:

    我们用a数组来代表题目中的数组,然后用q数组代表队列,其中q[i]代表的队列中第i - hh+ 1的点在数组a中的下标,比如当hh = 1的时候,i = 3,那么q[3]代表的就是队列里的第三个点在数组a中的下标

    通过样例来进行说明,本题要输出一行最小值和一行最大值,这里拿最小值去距举例:
    1 3 -1 -3 5 3 6 7
    我们可以观察到只要-1存在的话31就不会被输出出去,意味着这两个数是没有意义的,也就是说,当-1被输入进来后,我们可以把31直接删除,具体到队列中,就意味着,如果输入的元素要小于等于队尾元素的话,我们就可以把队尾元素删除,直到队尾元素要小于输入的元素或者队列为空就停止删除操作,这一步的代码为while (tt >= hh && a[q[tt]] >= a[i]) tt --;,同时如果i - k + 1 > q[hh],即队列头的坐标如果不在我们滑动窗口中的时候,我们就让hh ++;,最后说一下输出:当i遍历到第k个点的时候开始输出第一个最小值,因为我们的队列是从坐标0开始的,所以只有当i - 1 >= k的时候我们会开始输出最小值,因为队列中是满足单调递增的,而我们的队列维护的就是滑动窗口的区间,所以对头元素就是我们的最小值,注意对头元素的表示为a[q[hh]]


    AC代码

    #include <cstdio>
    
    using namespace std;
    
    const int N = 1000010;
    
    int q[N], a[N];
    
    int main()
    {
        int n, k;
        int hh = 0, tt = -1;
        scanf ("%d%d", &n, &k);
        
        for (int i = 0; i < n; i ++ ) scanf("%d", &a[i]);
        //计算最小值
        for (int i = 0; i < n; i ++ ) 
        {
            while (tt >= hh && a[q[tt]] >= a[i]) tt --;
            q[ ++ tt] = i;
            if (tt >= hh && q[hh] < i - k + 1) hh ++;
            if (i >= k - 1) printf("%d ", a[q[hh]]);
        }
        
        puts("");
        //计算最大值
        tt = -1, hh = 0;                    //这里一定要注意重新更新 hh 和 tt
        for (int i = 0; i < n; i ++ )
        {
            while (tt >= hh && a[q[tt]] <= a[i]) tt --;
            q[ ++ tt] = i;
            if (tt >= hh && q[hh] < i - k + 1) hh ++;
            if (i >= k - 1) printf("%d ", a[q[hh]]);
        }
        
        return 0;
    }
    

    二、时间复杂度

    关于单调队列的各操作时间复杂度以及证明,后续会给出详细的说明以及证明过程,目前先鸽了。

    展开全文
  • 详解单调队列算法

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

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

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

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

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

    队列

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

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

    在这里插入图片描述

    单调队列

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

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

    「单调递增队列」中「队尾」的操作与「单调递增栈」中「栈顶」的操作一致,即假设当前元素为 x,若队尾元素 <= x,则将 x 入队,否则不断弹出队尾元素,直至队尾元素 <= x。

    例如以 3 1 4 5 2 7 为例,若「队首」始终不弹出元素,则其具体过程如下图所示。

    在这里插入图片描述

    由此可知,「单调队列」与「单调栈」的最大区别就在于「队首」的操作,「何时将队首元素出队」是「单调队列」算法的关键。

    然而「队首」的操作往往具有多样性,并非一成不变,因此接下来我们以三道经典题型为例来进一步讲解该算法。

    习题讲解

    239. 滑动窗口最大值

    题目描述

    给你一个整数数组 nums,有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。

    返回滑动窗口中的最大值。

    示例 1

    输入:nums = [1,3,-1,-3,5,3,6,7], k = 3
    输出:[3,3,5,5,6,7]
    解释:
    滑动窗口的位置                最大值
    ---------------               -----
    [1  3  -1] -3  5  3  6  7       3
     1 [3  -1  -3] 5  3  6  7       3
     1  3 [-1  -3  5] 3  6  7       5
     1  3  -1 [-3  5  3] 6  7       5
     1  3  -1  -3 [5  3  6] 7       6
     1  3  -1  -3  5 [3  6  7]      7
    

    示例 2

    输入:nums = [1], k = 1
    输出:[1]
    

    示例 3

    输入:nums = [1,-1], k = 1
    输出:[1,-1]
    

    示例 4

    输入:nums = [9,11], k = 2
    输出:[11]
    

    示例 5

    输入:nums = [4,-2], k = 2
    输出:[4]
    

    提示

    • 1 <= nums.length <= 1e5
    • -1e4 <= nums[i] <= 1e4
    • 1 <= k <= nums.length

    题目讲解

    「滑动窗口中的最大 / 小值」是「单调队列」最为经典的应用,其它「单调队列」的题型大多从该模型演变而来,因此大家需要着重理解此题。

    由于本题求的是「滑动窗口中的最大值」,因此我们使用「单调递减队列来进行解决」。另外由于窗口大小为 k,所以当窗口右端点下标为 r 时,影响当前窗口最大值的元素下标范围为 [r-k+1, r]。

    由此我们可以制定「队首」弹出元素的规则,即当「队尾元素的下标 - 队首元素的下标 + 1」大于 k 时,弹出「队首」元素。

    接下来我们以 nums = [3 2 1 -1 2]、k = 3 为例,展示「单调递减队列」的具体执行过程。且为了便于展示,我们在「单调队列」中存储的是元素的下标,而不是元素的数值。

    在这里插入图片描述

    观察上述执行过程,我们可以发现元素入队分为两步,第一步是「不断弹出队尾元素」直至队尾元素代表的数值大于等于当前元素,第二步是「弹出队首元素」直至「当前元素下标 - 队首元素下标 + 1」小于等于 k。

    进一步观察可以发现,当前元素入队的两步操作结束后,以当前元素为右端点的窗口,其窗口最大值为「队首元素」所对应的数值。

    我们以当前元素为第四个元素(即 -1)为例来帮助大家理解。

    在这里插入图片描述

    此时队尾数值为 nums[3] = 1,即队尾数值大于等于当前元素,因此当前元素入队(队列中存储元素下标),如下图所示。

    在这里插入图片描述

    入队后「弹出队首元素」直至「当前元素下标 - 队首元素下标 + 1」小于等于 k,因此队首元素被弹出,最终状态如下图所示。

    在这里插入图片描述

    第四个元素完成上述两步入队操作后,队首元素下标为 2,其对应的数值 nums[2] = 2,当前窗口最大值 max([2 1 -1]) = 2。因此印证了刚才的结论,即当前元素入队的两步操作结束后,以当前元素为右端点的窗口,其窗口最大值为「队首元素」所对应的数值。

    由此我们可以发现「单调队列」的核心功能为「求出数组中每一个元素其固定区间范围内的最大 / 小值」。并且由于每个元素出队、入队最多一次,因此总的时间复杂度为 O(n)。

    根据上述算法即可解决本题,具体实现细节见下述代码。

    代码实现

    class Solution {
    public:
        vector<int> maxSlidingWindow(vector<int>& nums, int k) {
            int len = nums.size(), l = 0, r = -1;
            vector<int> q(len, 0), ans;
            for (int i = 0; i < len; i++) {
                while (l <= r && nums[q[r]] < nums[i]) r--;
                q[++r] = i;
                if (i-q[l]+1 > k) l++;
                if (i >= k-1) ans.push_back(nums[q[l]]);
            }
            return ans;
        }
    };
    

    1425. 带限制的子序列和

    题目描述

    给你一个整数数组 nums 和一个整数 k ,请你返回「非空」子序列元素和的最大值,子序列需要满足:子序列中每两个「相邻」的整数 nums[i] 和 nums[j],它们在原数组中的下标 i 和 j 满足 i < j 且 j - i <= k 。

    数组的子序列定义为:将数组中的若干个数字删除(可以删除 0 个数字),剩下的数字按照原本的顺序排布。

    示例 1

    输入:nums = [10,2,-10,5,20], k = 2
    输出:37
    解释:子序列为 [10, 2, 5, 20] 。
    

    示例 2

    输入:nums = [-1,-2,-3], k = 1
    输出:-1
    解释:子序列必须是非空的,所以我们选择最大的数字。
    

    示例 3

    输入:nums = [10,-2,-10,-5,20], k = 2
    输出:23
    解释:子序列为 [10, -2, -5, 20] 。
    

    提示

    • 1 <= k <= nums.length <= 1e5
    • -1e4 <= nums[i] <= 1e4

    题目讲解

    本题求解的是最大「非空」子序列元素和,且相邻两个元素坐标差小于等于 k。由于题目的主体是子序列,因此我们采取一种「增量式」的思想来进一步思考。

    假设当前有一个子序列 A,现在想在 A 后面再添加一个元素 x,则我们只需要考虑 x 和 A 中最后一个元素的坐标差是否小于等于 k,而不用考虑 A 中的所有元素。更明确地说,对于子序列 A,我们只需要记录它的元素和与最后一个元素的下标即可。

    基于上述的思考,不难想到使用动态规划的算法,令 f[i] 表示以 nums[i] 为子序列最后一个元素时的最大元素和,则可以得到如下递推公式:
    f [ i ] = max ⁡ ( f [ j ] , 0 ) + n u m s [ i ]     ( i − k ≤ j < i ) f[i]=\max(f[j],0)+nums[i]\ \ \ (i-k\leq j<i) f[i]=max(f[j],0)+nums[i]   (ikj<i)

    根据上述公式,我们可以得到一种暴力的做法,即对于每一个 i,向前枚举合法的 j 来更新 f[i],时间复杂度为 O(nk)。

    观察题目中的数据范围,暴力做法很明显无法通过,因此我们考虑如何优化。

    f[i] 由前面 k 个数中的最大值转移而来,因此不难想到使用「单调队列」算法来进行优化。用「单调队列」来维护 f 数组中大小为 k 的窗口的最大值即可完成此题,时间复杂度优化至 O(n),具体细节见代码。

    通过此题,我们可以更深刻地意识到,「单调队列」在求取「数组中每一个元素其固定区间范围内的最大 / 小值」的作用。而也正是该功能,使得「单调队列」常作为「动态规划」的一种优化手段出现在面试题中。

    代码实现

    class Solution {
    public:
        int constrainedSubsetSum(vector<int>& nums, int k) {
            int len = nums.size(), l = 0, r = -1, ans = nums[0];
            vector<int> q(len, 0);
            for (int i = 0; i < len; i++) {
                if (l <= r && i - q[l] > k) l++;
                if (l <= r) nums[i] = max(nums[i], nums[i] + nums[q[l]]);
                ans = max(ans, nums[i]); 
                while (l <= r && nums[q[r]] < nums[i]) r--;
                q[++r] = i;
            }
            return ans;
        }
    };
    

    862. 和至少为 K 的最短子数组

    题目描述

    返回 A 的最短的非空连续子数组的长度,该子数组的和至少为 K 。

    如果没有和至少为 K 的非空子数组,返回 -1。

    示例 1

    输入:A = [1], K = 1
    输出:1
    

    示例 2

    输入:A = [1,2], K = 4
    输出:-1
    

    示例 3

    输入:A = [2,-1,2], K = 3
    输出:3
    

    提示

    • 1 <= A.length <= 50000
    • -1e5 <= A[i] <= 1e5
    • 1 <= K <= 1e9

    题目讲解

    本题求解的是元素和大于等于 K 的最短非空连续子数组,由于涉及连续子数组和的求取,所以先对 A 做一个前缀和。

    令 B 为 A 的前缀和数组,即 A 在 [x, y] 区间的元素和等于 B[y] - B[x-1]。又因为我们需要求解元素和大于等于 K 的最短连续子数组,即对于 B[y] 来说,找到最大的 x 满足 0 <= x < y 且 B[y] - B[x] >= K,也就是说,我们既希望 B[x] 小又希望 x 大。

    基于上述观察,我们可以维护一个单调递增队列 [x1, x2, …, xp] 存储所有可能更新答案的下标 x(左边为队首)。队列满足从左至右,下标递增且下标对应的 B 中元素值也递增。

    假设当前元素为 B[y],若 B[xp] > B[y] 则弹出,因为 y 比 xp 更大且 B[y] 比 B[xp] 更小,即 y 一定比 xp 更优。基于该策略不断弹出队尾元素,直至条件不再满足。

    对于队首元素来说,若 B[y] - B[x1] >= K,则弹出 x1 并更新答案 ans = min(ans, y - x1)。因为 y 是不断变大的,就算之后存在 y’ > y 满足 B[y’] - B[x1] >= K,y 距 x1 仍近于 y’,因此可以直接将 x1 弹出而不影响答案。基于该策略不断弹出队首元素,直至条件不再满足。

    另外,上述算法未考虑到区间 [1, y] 的情况,因此若 B[y] >= K,则更新答案 ans = min(ans, y)。

    观察上述算法,可以发现队尾操作与基础题「滑动窗口」没有区别,主要变化在于「队首弹出元素」的条件,而本题也正是通过对该条件的修改使得题目思维难度变大。

    代码实现

    class Solution {
    public:
        int shortestSubarray(vector<int>& A, int K) {
            int len = A.size(), l = 0, r = -1, ans = len+1;
            vector<int> q(len, 0);
            for (int i = 1; i < len; i++) A[i] += A[i-1];
            for (int i = 0; i < len; i++) {
                while (l <= r && A[q[r]] > A[i]) r--;
                q[++r] = i;
                while (A[q[r]]-A[q[l]] >= K) {
                    ans = min(ans, q[r]-q[l]);
                    l++;
                }
                if (A[i] >= K) ans = min(ans, i+1);
            }
            if (ans == len+1) ans = -1;
            return ans;
        }
    };
    

    总结

    通过上述三道例题的讲解,希望大家对于「单调队列」有了更多的了解,其实「单调队列」就是在「单调栈」的基础上加了一个「弹出队首」的操作,虽然该操作的添加极大地增加了该算法的多样性。

    不过作为初学者,大家只需要理解「单调队列」在「滑动窗口」问题上的应用即可,即在 O(n) 时间复杂度内求出数组中每一个元素其固定区间范围的最大 / 小值。

    至此我们完成了两大基础线性数据结构的讲解(单调栈与单调队列),这两个数据结构的变化较多,大家需要在日后刷题的过程中进一步地感受与体会,祝大家日益精进,刷题愉快!

    展开全文
  • 单调栈与单调队列

    2022-02-22 09:36:44
    单调栈与单调队列的原理介绍加代码实现。


    单调栈与单调队列

    单调栈就是栈内元素满足单调性的栈结构。此处的单调性分为单调递增与单调递减

    如何维护一个单调栈:
    单调递增栈:在保持栈内元素单调递增的前提下(如果栈顶元素大于要入栈的元素,将将其弹出),将新元素入栈。

    单调递减栈:在保持栈内元素单调递减的前提下(如果栈顶元素小于要入栈的元素,则将其弹出),将新元素入栈。

    什么时候使用单调栈:

    • 给定一个序列,求序列中的每一个数左边/右边第一个比他小/比他大的数;

    • 给定一个序列,求序列中的每一个数左边/右边第一个比他小/比他大的数在什么地方;

      注:寻找位置时(下标时)stk栈存储的是下标,而不是数值

    一、单调栈

    1.单调递增栈

    单调递增栈应用:从左往右遍历——可以找到第一个比它小的元素的位置

    单调递增栈就是栈内元素满足单调递增,假设当前元素为 x ,若栈顶元素 < x ,则将x 入栈否则(栈顶元素 >= x)不断弹出栈顶元素,直至栈顶元素 < x

    (1)单调递增栈求左边第一个比它小的数

    求序列中每一个数左边第一个比它小的数

    for(int i = 1; i <= n; i ++)
    {
    	int x;
    	cin >> x;
    	while(tt != 0 && stk[tt] >= x) tt --;
    	if(tt == 0) cout << "-1" << " ";
    	else cout << stk[tt] << " ";
    	
    	stk[++ tt] = x;
    }
    

    (2)单调递增栈求左边第一个比它小的数的位置

    求序列中每一个数左边第一个比它小的数的位置

        stack<int> s;
        for(int i = 1; i <= n; ++i)
        {
            while(s.size() && a[s.top()] >= a[i]) s.pop();
            if(s.empty()) l[i] = 0;
            else l[i] = s.top();
            s.push(i);
        }
    // 数组模拟栈    
        for(int i = 1; i <= n ; i ++ )
        {
            while(tt != 0 && a[stk[tt]] >= a[i]) tt--;
            if(tt == 0) l[i] = 0; // 栈为空,不存在则记为0
            else l[i] = stk[tt]; // 符合要求l[i]记录对应栈顶下标
            stk[++ tt] = i; // 最后当前扫描到的下标入栈
        }
    

    下面以3 1 4 5 2 7为例解释单调递增栈

    【文字描述】

    image

    image

    【动图展示】

    通过观察原始序列 3 1 4 5 2 7,对比结果的单调栈1 2 7可以发现 1 是 2 左边第一个小于等于它的数,稍加思考后,我们可以得知当一个数字被放入单调递增栈时,其栈内左边的数是它在原始序列中,左边第一个小于等于它的数。

    【acwing 单调栈】

    给定一个长度为 N 的整数数列,输出每个数左边第一个比它小的数,如果不存在则输出 −1。

    输入格式
    第一行包含整数 N,表示数列长度。

    第二行包含 N 个整数,表示整数数列。

    输出格式
    共一行,包含 N 个整数,其中第 i 个数表示第 i 个数的左边第一个比它小的数,如果不存在则输出 −1。

    数据范围
    1≤N≤105
    1≤数列中元素≤109
    输入样例:
    5
    3 4 2 7 5
    输出样例:
    -1 3 -1 2 2

    暴力代码:超时

    #include<iostream>
    
    using namespace std;
    const int N = 1e5 + 10;
    int a[N];
    
    int main() {
        int n;
        cin >> n;
        for (int i = 0; i < n; i++) scanf("%d", &a[i]);
        printf("-1 ");
        
        for (int i = 1; i < n; i++) {
            for (int j = i - 1;; j--) {
                if (j >= 0 && a[j] < a[i]) {
                    cout << a[j] << " ";
                    break;
                } else if (j < 0) {
                    cout << "-1 ";
                    break;
                }
            }
        }
        
        return 0;
    }
    
    

    单调栈:O(n)

    #include<iostream>
    
    using namespace std;
    const int N = 100000+10;
    int stk[N],tt;
    int main()
    {
        int n;
        cin>>n;
        for(int i = 1; i <= n; i++)
        {
            int x;
            cin>>x;
            while(tt != 0 && stk[tt] >= x) tt--; //如果栈顶元素大于当前待入栈元素,则出栈
            if(tt == 0) cout<<"-1 "; // 栈为空(无满足要求的数)
            else cout<<stk[tt]<<" "; // 满足要求输出栈顶元素
            
            stk[++ tt] = x; // 当前元素入栈
        }
        
        return 0;
    }
    

    寻找位置:

    假设有一个单调递增的栈 stk和一组数列: a = { 5 3 7 4}
    用数组L[i]表示 第i个数向左遍历的第一个比它小的元素的位置

    如何求L[i]?

    3.1 朴素的算法 O(n^2)
    可以按顺序枚举每一个数,然后再依此向左遍历。 但是当数列单调递减时,复杂度是严格的O(n^2)。

    3.2 单调栈 O(n)
    我们按顺序遍历数组(i : 1 -> n),然后构造一个单调递增栈。栈中存放的是元素下标,而非元素本身。

        {5 3 7 4}
    

    (1)i = 1时,因为栈为空,L[1] = 0,此时再将第一个元素的位置下标1存入栈中。
    此时栈中情况:

    在这里插入图片描述

    (2)i = 2时,因当前元素a[i] = 3小于栈顶元素下标1对应的元素a[1] = 5,故将下标1弹出栈, 此时栈为空 ,故L[2] = 0 。然后将元素3对应的位置下标2存入栈中。
    此时栈中情况:

    在这里插入图片描述

    (3)i = 3时,因当前元素a[i] = 7大于栈顶元素下标2对应的元素a[2] = 3,故
    L[3] = stk[tt] = 2 (栈顶元素的值,说明第一个比它小的元素的下标为多少),然后将元素7对应的下标3存入栈 。
    此时栈中情况:

    在这里插入图片描述

    (4)i = 4时,因当前元素a[i] =4小于栈顶元素下标3对应的元素a[3] = 7,为保持单调递增的性质,应将栈顶元素下标3弹出 ,而当前元素a[i] =4大于弹出元素后的栈顶元素下标2对应的元素a[2] = 3,不需要再继续弹出, 此时 L[4] = stk[tt] = 2;然后将元素4对应的下标4存入栈。
    此时栈中情况:
    在这里插入图片描述

    (5)至此 算法结束

    对应的结果:
    a : 5 3 7 4
    L : 0 0 2 2

    下一个单调递减栈的模拟画图过程也大致同上,只不过是从后往左遍历罢了!

    【将上题目答案改成寻找位置】

    #include<iostream>
    
    using namespace std;
    const int N = 100000+10;
    int stk[N],tt,l[N],a[N];
    int main()
    {
        int n;
        cin>>n;
        for(int i = 1; i <= n; i++) cin>>a[i];
        for(int i = 1; i <= n; i++)
        {
            while(tt != 0 && a[stk[tt]] >= a[i]) tt--; //如果栈顶元素大于当前待入栈元素,则出栈
            if(tt == 0) l[i] = 0; // 栈为空(无满足要求的数)
            else l[i] = stk[tt]; // 满足要求输出栈顶元素
            
            stk[++ tt] = i; // 当前元素入栈
        }
        for(int i = 1; i <= n; i++) cout<<l[i]<<" ";
        return 0;
    }
    

    2.单调递减栈

    单调递减栈应用:从右往左遍历————寻找左边边第一个比当前元素大的数/数的位置

    (1)单调递减栈求左边第一个比它大的数

    求序列中每一个数左边第一个比它小的数

    for(int i = 1; i <= n; i ++)
    {
    	int x;
    	cin >> x;
    	while(tt != 0 && stk[tt] <= x) tt --;
    	if(tt == 0) cout << "-1" << " ";
    	else cout << stk[tt] << " ";
    	
    	stk[++ tt] = x;
    }
    

    (2)单调递减栈求左边第一个比它大的数的位置

        // 单调递减栈:从右往左遍历————寻找右边第一个比当前元素大的数的位置
        for(int i = n; i >= 0; i -- )
        {
            while(tt != 0 && a[stk[tt]] <= a[i]) tt--;
            if(tt == 0) l[i] = 0; // 栈为空,不存在则记为0
            else l[i] = stk[tt]; // 符合要求l[i]记录对应栈顶下标
            stk[++ tt] = i; // 最后当前扫描到的下标入栈
        }
    

    【acwing 仰视奶牛】

    约翰有 N 头奶牛,编号为 1 到 N。

    现在这 N 头奶牛按编号从小到大的顺序站成了一排,其中奶牛 i 的身高为 Hi。

    现在,每头奶牛都向它的右侧望向那些编号较大的奶牛,对于奶牛 i 如果存在一头奶牛 j 满足 i<j 并且 Hi<Hj,那么我们称奶牛 i 需要仰视奶牛 j。

    请你求出每头奶牛的最近仰视对象。

    输入格式

    第一行包含整数 N。

    接下来N 行,每行包含一个整数 Hi,其中第 i 行的数为编号为 i 的奶牛的高度。

    输出格式

    共 N 行,每行输出一个整数,其中第 i 行的输出整数表示编号为 i 的奶牛的最近仰视对象的编号,如果不存在仰视对象,则输出 00。

    数据范围

    1≤N≤105,
    1≤Hi≤106

    输入样例:

    6
    3
    2
    6
    1
    1
    2

    输出样例:

    3
    3
    0
    6
    6
    0

    #include<iostream>
    
    using namespace std;
    const int N = 100000+10;
    int tt, a[N], l[N], stk[N]; //stk[N]: 存储栈顶下标;l[N]记录答案
    
    int main()
    {
        int n;
        cin>>n;
        for(int i = 1; i <= n; i++) scanf("%d",&a[i]);
        
        // 单调递减栈:从右往左遍历————寻找右边第一个比当前元素大的数的位置
        for(int i = n; i >= 0; i -- )
        {
            while(tt != 0 && a[stk[tt]] <= a[i]) tt--;
            if(tt == 0) l[i] = 0; // 栈为空,不存在则记为0
            else l[i] = stk[tt]; // 符合要求l[i]记录对应栈顶下标
            stk[++ tt] = i; // 最后当前扫描到的下标入栈
        }
        
        for(int i = 1; i <= n; i++) printf("%d\n", l[i]);
        return 0;
    }
    

    总结

    至此我们可以解答最开始的疑问,单调栈的根本作用在于求得「每一个数字在原始序列中左 / 右边第一个大于 / 小于它自身的数字或者位置」,并且由于每一个数字只会入栈一次且最多出栈一次,因此总的时间复杂度为 O ( n ) 。

    一定要手动模拟画出过程图。记住:入栈操作是最后一步,别先入栈了在判断!

    二、单调队列(单调双端队列)

    说单调队列,那我们就先说说这个单调队列是个什么物种。单调队列从字面上看,无非就是有某种单调性的队列,没错,这就是所谓的单调队列。 单调队列它分两种,一种是单调递增的,另外一种是单调递减的。

    在这搬出百度百科的解释:不断地向缓存数组里读入元素,也不时地去掉最老的元素,不定期的询问当前缓存数组里的最小的元素。

    用单调队列来解决问题,一般都是需要得到当前的某个范围内(连续的字序)的最小值或最大值

    队列中元素之间的关系具有单调性,且队首和队尾都可以进行出队操作,只有队尾可以进行入队操作。
    用处:

    • 对于维护好的单调队列,对内元素是有序的,那么取出最大值(最小值)的复杂度为O(1)
    • 可以拿来优化DP(…)

    单调队列:通俗的讲就是以一个固定长度的窗口在数列上移动,(这个固定的长度是题目给的,队首元素在队列中的位置与队尾元素在队列的位置之差若大于这个固定长度,就得将队首元素弹出)

    【acwing滑动窗口】

    给定一个大小为n≤106 的数组。

    有一个大小为 kk 的滑动窗口,它从数组的最左边移动到最右边。

    你只能在窗口中看到 kk 个数字。

    每次滑动窗口向右移动一个位置。

    以下是一个例子:

    该数组为 [1 3 -1 -3 5 3 6 7],k 为 3。

    窗口位置最小值最大值
    [1 3 -1] -3 5 3 6 7-13
    1 [3 -1 -3] 5 3 6 7-33
    1 3 [-1 -3 5] 3 6 7-35
    1 3 -1 [-3 5 3] 6 7-35
    1 3 -1 -3 [5 3 6] 736
    1 3 -1 -3 5 [3 6 7]37

    你的任务是确定滑动窗口位于每个位置时,窗口中的最大值和最小值。

    输入格式

    输入包含两行。

    第一行包含两个整数 n 和 k,分别代表数组长度和滑动窗口的长度。

    第二行有 n 个整数,代表数组的具体数值。

    同行数据之间用空格隔开。

    输出格式

    输出包含两个。

    第一行输出,从左至右,每个位置滑动窗口中的最小值。

    第二行输出,从左至右,每个位置滑动窗口中的最大值。

    输入样例:

    8 3
    1 3 -1 -3 5 3 6 7

    输出样例:

    -1 -3 -3 -3 3 3
    3 3 5 5 6 7

    image

    image

    #include<iostream>
    
    using namespace std;
    
    const int N = 1e6 + 10; // 注意题目数组的范围
    
    int a[N], q[N];
    
    int main()
    {
        int n, k;
        cin>>n >> k;
        for(int i = 0; i < n; i++) cin>>a[i];
        
        int hh = 0, tt = -1;
        for(int i = 0; i < n; i++) // 暴力模拟
        {	
            
            // 判断对头下标是否超出了 i - k + 1 ~ i 这个范围,若超出则去掉队头下标
            // 判断是否在(i - k + 1, i)这个范围内 下标从0开始的因此要加1
            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) cout<< a[q[hh]]<<" ";
            
        }
        
        cout<<endl;
        
        hh = 0, tt = -1; // 跟上述是对称的
        for(int i = 0; i < n; i++) // 暴力模拟
        {
            // 判断是否滑出窗口
            if(hh <= tt && i - k + 1 > q[hh]) hh ++; 
            // 单调递减队列求当前区间最da值
            while(hh <= tt && a[q[tt]] <= a[i]) tt --;
            // 当前下下标入队
            q[++ tt] = i;
            
            //输出窗口(每个区间范围的最da值)
            if(i >= k - 1) cout<< a[q[hh]]<<" ";
            
        }
        
        return 0;
    }
    

    单调栈与单调队列总结:

    (1)先用栈/队列来暴力模拟问题,即清除暴力朴素算法

    (2)观察栈/队列中那些元素是没有用的,将这些没有用的数全部删掉

    (3)剩下的元素具有单调性就可以进行优化

    1. 求极值:端点
    2. 找某个数——二分

    参考文献:
    acwing算法基础课

    展开全文
  • 数组模拟单调栈和单调队列——Java版前言1 单调栈2 单调队列参考 前言 为什么写这篇文章呢?是因为笔者今天在写单调队列题目239. Sliding Window Maximum时,发现使用双端队列的时效性有点差强人意,所以尝试利用...
  • 第5章 单调队列优化动态规划(2021.08.19).pdf
  • 单调队列(PASCAL)-2020.06.09.pdf
  • 本人自己做的类,虽说只是测试版,但已经可以胜任一部分任务了 PS:双向队列是基础类,单调队列、单调栈是结果类
  • 【C++】单调队列 详解

    2022-02-10 22:46:17
    目录单调队列1.1 单调队列介绍1.2 单调队列的应用1.2.1 滑动窗口最大值1.2.1.1 题目描述1.2.1.2 结题思路方法一(优先队列)方法二 (单调队列)1.3 单调队列的模拟实现1.4 其他例题 单调队列 1.1 单调队列介绍 单调...
  • 第5章 单调队列优化动态规划(2021.08.23).pdf
  • 单调队列详解

    2021-07-14 09:26:59
    顾名思义,单调队列就是在队列的基础上,维护一个单调的序列。可以用来维护(给定大小的)区间的最值,其时间复杂度为o(n),其中n为序列的元素个数。 性质 众所周知,单调性有单调递增和单调递减两种,相应的单调...
  • 多重背包单调队列优化问题.pdf
  • 多重背包问题的单调队列优化,适合对多重背包问题有一定了解的人阅读
  • 单调栈、单调队列(超详细)

    千次阅读 多人点赞 2022-02-15 13:46:44
    单调栈、单调队列 单调栈 单调递增栈:栈中数据入栈或出栈的序列为单调递减序列; 单调递减栈:栈中数据入栈或出栈的序列为单调递增序列。 维护单调递增栈:遍历数组中每一个元素,执行入栈:每次入栈前先检验栈顶...
  • 多重背包问题的单调队列优化深度解析
  • 队列,单调队列

    2021-08-11 10:08:02
    假溢出:顺序队列因多次入队列和出队列操作后出现的尚有存储空间但不能进行入队列操作的溢出。 真溢出:顺序队列的最大存储空间已经存满二又要求进行入队列操作所引起的溢出。 循环队列 循环队列的判...
  •   但是实际情况中,我们维持的单调栈与栈的数据结构式吻合的,而维持的单调队列则大部分可能都是双端队列,那么看到一个问题,我们如何确定到底使用来个结构来维持一个单调的序列的? 单调栈   我想有很多小伙伴...
  • 借助单调性处理问题,及时排除不可能的策略,以保持策略集合的有效性、秩序性。 单调栈 例题:POJ2559 直方图中的最大矩形(在一条直线上有若干个宽度为1的矩形,求包含于这些矩形的并集内部的最大的矩形的面积)。 ...
  • 单调队列(stl)

    2021-08-14 16:21:00
    单调队列是一种队列内的元素有单调性(单调递增或者单调递减)的队列,答案(也就是最优解)就存在队首,而队尾则是最后进队的元素。因为其单调性所以经常会被用来维护区间最值或者降低DP的维数已达到降维来减少空间...
  • 多重背包单调队列优化问题多重背包单调队列优化问题多重背包单调队列优化问题多重背包单调队列优化问题多重背包单调队列优化问题多重背包单调队列优化问题多重背包单调队列优化问题多重背包单调队列优化问题多重背包...
  • 单调栈:栈内的元素按照某种方式排序下单调递增或单调递减,如果新入栈的元素破坏的单调性,就弹出栈内元素,直到满足单调性。 单调栈分为单调递增栈和单调递减栈: 单调递增栈:栈中数据出栈的序列为单调递减序列...
  • 单调队列(java)

    2021-02-21 13:41:07
    单调队列,顾名思义,就是队列中的值要么单调递增要么单调递减。之前做题的时候对这个并没有太在意,但是今天的每日抑题用堆实现的时候发现太耗时了,借此机会好好学一下单调队列。 leetcode1438 求满足条件的最长...
  • 单调队列优化DP

    2021-07-21 20:24:43
    一、单调队列 单调队列,即单调递减或单调递增的队列。使用频率不高,但在有些程序中会有非同寻常的作用。——百度百科 重点在哪里? 使用频率不高 单调递减或单调递增的队列。 单调队列是一个双端队列,一般来说...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 41,756
精华内容 16,702
关键字:

单调队列

友情链接: Files and Codes.zip