大家好,又见面了,我是你们的朋友全栈君。
- 博客主页: 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] [i−k+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[i−1][k]+a[i]∗j),j−1≤k≤min(j+s−1,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)] [j−1,min(j+s−1,w)]求最大值,所以就要再进行一次循环求最大值(见下文代码)
所以共三层循环,复杂度太大,需要进行优化。
以下是对max的优化
优化限定区间长度的max
值操作考虑单调队列
q[]
中存储的是最大值的下标,用f[i-1][hh]
得到最大值
维护限定区间最大值为什么从右向左转移?
因为区间要求是 [ j − 1 , m i n ( j + s − 1 , w ) ] [j-1, min(j+s-1,w)] [j−1,min(j+s−1,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账号...