【单调队列】数据结构之单调队列详解

【单调队列】数据结构之单调队列详解单调队列1.初步认识单调队列是一个数据结构,并不是STL里面的内容。单调队列为何说单调,因为是队列中的元素始终保持着单增或者单减的特性。(注意始终保持这四个字)简单的sort排序就可以让一个序列有序了,为何又多此一举多出来个单调队列实现类似的功能呢?其实单调队列不只是做到了排序,还可以实现一个功能:在每次加入或者删除元素时都保持序列里的元素有序,即队首元素始终是最小值或者最大值,这个功能非常重要,单调队列我们就是使用的这个功能。举个例子:我们依次加入5个元素,分别为5,8,2,4,1那么我们假

大家好,又见面了,我是你们的朋友全栈君。

  • 博客主页: 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

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/152986.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)


相关推荐

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号