单调队列思维导图_编号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; }

相关思维导图模板

环境空气污染和胰岛素敏感性之间的纵向关联：来自KORA队列研究的结果

免费使用模版

小柴奶黄包

3.15

树图思维导图提供环境空气污染和胰岛素敏感性之间的纵向关联：来自KORA队列研究的结果在线思维导图免费制作，点击“编辑”按钮，可对环境空气污染和胰岛素敏感性之间的纵向关联：来自KORA队列研究的结果进行在线思维导图编辑，本思维导图属于思维导图模板主题，文件编号是：05a1570de9aff1ce3943db94321ac5c5

长期暴露于低水平的环境空气污染和中风和冠心病的发病率：在过去的项目内，对6个欧洲队列的汇总分析

免费使用模版

小柴奶黄包

1.11

树图思维导图提供长期暴露于低水平的环境空气污染和中风和冠心病的发病率：在过去的项目内，对6个欧洲队列的汇总分析在线思维导图免费制作，点击“编辑”按钮，可对长期暴露于低水平的环境空气污染和中风和冠心病的发病率：在过去的项目内，对6个欧洲队列的汇总分析进行在线思维导图编辑，本思维导图属于思维导图模板主题，文件编号是：aeb214df5055d8c5f449655fbfd81f7d