单调队列思维导图_编号w1685758-TreeMind树图

笔灵AI论文写作三步搞定，GO>>

当前位置:树图

思维导图模板

高校与高等教育

其他学科

单调队列思维导图

免费下载

免费使用文件

Mr.Xu

浏览量：4

2023-07-23 08:53:33

已被使用2次

查看详情

单调队列

树图思维导图提供单调队列在线思维导图免费制作，点击“编辑”按钮，可对单调队列进行在线思维导图编辑，本思维导图属于思维导图模板主题，文件编号是：b6af5e3d6321356375158727645c09ff

单调队列

举报/反馈

思维导图大纲

单调队列思维导图模板大纲

用来求滑动窗口最值问题

例：在n个整数中，求每一个长为m区间中的最小值

#include<bits/stdc++.h> using namespace std; const int N=1e6+10; int a[N],n,m; deque<int> deq; int main(){ scanf("%d%d",&n,&m); for(int i=1;i<=n;i++) scanf("%d",&a[i]); for(int i=1;i<=m;i++){ while(!deq.empty()&&a[deq.back()]>=a[i]) deq.pop_back(); deq.push_back(i); } printf("%d ",a[deq.front()]); for(int i=m+1;i<=n;i++){ if(i-deq.front()==m) deq.pop_front(); while(!deq.empty()&&a[deq.back()]>=a[i]) deq.pop_back(); deq.push_back(i); printf("%d ",a[deq.front()]); } return 0; }

要点

维护区间最值

设ai表示第i天发放蛋挞的美味度，f[i]表示第天选择的最大美味度

区间出现平移

队首指针会随着队首元素出队右移，队尾指针会随着队尾入队和出队右移和左移

去除冗余状态

区间中的两个元素a和aj，如果满足i>j&&ai>aj，则ai跟aj比“既新鲜又美味”，aj没有存在的必要，可以直接出队

保持队列单调

由3得知队列中保留的元素是单调的，如例题(美味蛋挞)中就是单调递减的

前最优值为队头元素的值

如例题中的队列最大值在队首

求过了一维的最大最小值，现在我们来看看二维的（输入一个二维矩阵，求每个22（也可以是xx)的矩阵中最大，最小值

我们可以先求出每行最大最小值，然后在此基础上求每列的，最后就求出了矩阵的

#include<bits/stdc++.h> using namespace std; deque<int> deq,deq1; int n,m,cnt1,a[105][105],X[105][105],x[105][105],cnt,ANS[105][105],ans[105][105],t; int main(){ scanf("%d%d%d",&n,&m,&t); for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) scanf("%d",&a[i][j]); //输入 for(int f=1;f<=n;f++){ cnt=0; deq.clear(); deq1.clear(); for(int i=1;i<=m;i++){ if(!deq.empty()&&i-deq.front()==t) deq.pop_front(); if(!deq1.empty()&&i-deq1.front()==t) deq1.pop_front(); while(!deq.empty()&&a[f][deq.back()]<=a[f][i]) deq.pop_back(); while(!deq1.empty()&&a[f][deq1.back()]>=a[f][i]) deq1.pop_back(); deq.push_back(i); deq1.push_back(i); if(i>=t) X[f][++cnt]=a[f][deq.front()]; if(i>=t) x[f][cnt]=a[f][deq1.front()]; } } //求每一行最大值，最小值 for(int f=1;f<=cnt;f++){ cnt1=0; deq.clear(); deq1.clear(); for(int i=1;i<=n;i++){ if(!deq.empty()&&i-deq.front()==t) deq.pop_front(); if(!deq1.empty()&&i-deq1.front()==t) deq1.pop_front(); while(!deq.empty()&&a[deq.back()][f]<=X[i][f]) deq.pop_back(); while(!deq1.empty()&&a[deq1.back()][f]>=x[i][f]) deq1.pop_back(); deq.push_back(i); deq1.push_back(i); if(i>=t) ANS[++cnt1][f]=X[deq.front()][f]; if(i>=t) ans[cnt1][f]=x[deq1.front()][f]; } } //求每一列最大，最小值（在每一行的基础上） for(int i=1;i<=cnt1;i++){ for(int j=1;j<=cnt;j++){ printf("%d ",ANS[i][j]); } printf("\n"); } printf("\n"); for(int i=1;i<=cnt1;i++){ for(int j=1;j<=cnt;j++){ printf("%d ",ans[i][j]); } printf("\n"); } return 0; }

单调队列同时可以用来优化dp

例题-跳跃的小鸟(P3572)

这道题的思路一开始其实是基础dp，但敲出来之后发现数据这么大，一定会爆（毕竟双重循环外面再套一个数据组数）这时我们就可以思考一下用单调队列来优化他，第i棵树一定是由前面的树飞过来的。所以我们可以维护一个单调队列来存储，注意多组数据的清空以及非空判断（被卡了半个小时没找到）

#include<bits/stdc++.h> using namespace std; int f[1000005],d[1000005],k[30]; deque<int> deq; int main(){ int n,q; scanf("%d",&n); for(int i=1;i<=n;i++) scanf("%d",&d[i]); scanf("%d",&q); for(int i=1;i<=q;i++) scanf("%d",&k[i]); for(int l=1;l<=q;l++){ deq.clear(); memset(f,127/2,sizeof(f)); f[1]=0; deq.push_back(1); for(int i=2;i<=n;i++){ if(!deq.empty()&&i-deq.front()>k[l]) deq.pop_front(); if(!deq.empty()) f[i]=f[deq.front()]+(d[deq.front()]<=d[i]); else f[i]=f[i]; while(!deq.empty()&&(f[deq.back()]>f[i]||(f[i]==f[deq.back()]&&d[deq.back()]<=d[i]))) deq.pop_back(); deq.push_back(i); } printf("%d\n",f[n]); } return 0; }

相关思维导图模板

早期接触农业、生物多样性和绿地与炎症性肠病风险之间的关系：一项基于人群的队列研究

免费使用模版

U263263693

4.81

树图思维导图提供早期接触农业、生物多样性和绿地与炎症性肠病风险之间的关系：一项基于人群的队列研究在线思维导图免费制作，点击“编辑”按钮，可对早期接触农业、生物多样性和绿地与炎症性肠病风险之间的关系：一项基于人群的队列研究进行在线思维导图编辑，本思维导图属于思维导图模板主题，文件编号是：75be218ffb126e173bd37cfbce4760ff