devbox
代码探险家
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

浅谈简单的数据结构1（单调队列，单调栈，优先队列）（c++）

作者：代码探险家 | 2024-08-02 08:02:03

赞

踩

浅谈简单的数据结构1（单调队列，单调栈，优先队列）（c++）

*_*又是被机房信息轰炸的一天，我太难了

栈和队列

详情参见浅谈STL标准库及应用（c++）

栈是一个只能在一端插入或删除元素的线性表。

队列是一个只能在一端插入元素，另一端删除元素的线性表。

栈中元素“先进后出”，队列中则是“先进先出”。 栈和队列正常可直接用数组模拟。 STL 中也提供了相应的容器，这里展示部分常用函数。 stack 应用较少，大部分时候会选择 vector 替代。 朴素的栈和队列作为算法单独考察的情况很少，更多是作为工具在各种算法中起到辅助作用。如 tarjan 求强连通分量时会用到栈，大部分bfs 流程、spfa 等都会用到队列。 

双端队列

双端队列在队列的基础上，额外支持了在队首插入和在队尾删除两种操作。（在队首插入的操作不太常见） 正常数组模拟额外支持队尾删除即可。如果需要在队首插入，可能需要一个叫“循环队列”的小技巧。

同样，在 STL 中也提供了双端队列的容器。 其中 resize() 函数相对复杂，正常来说记住 resize(0) 是清空就行。 stack 和 queue 不支持 clear() 函数。

应用

正常来讲双端队列的直接应用并不多。（没什么大用） spfa 一些所谓的优化会用到双端队列。但正常也不建议用 spfa，不过多赘述。

单调队列

定义：队列中每个元素均小于或均大于其后面元素的队列。

能否有相等元素需要就题论题，暂且不考虑。

我们从一道用烂的经典例题入手，初步的了解其功能

例题讲解

（1）P1886 滑动窗口 /【模板】单调队列

题目传送门

格式化题面

给定长为 n 的序列 a 和正整数 k，你需要求出任意相邻的 k 个数中的最大值。 n,k≤2×10^7

思路

显然可以暴力对每个区间求最大值。求区间最大值的方法很多，复杂度基本不低于 O(nlogn)，不过多赘述。 对这种问题有一种很经典的思路，考虑相邻两个区间的变化对答案的影响。 一般的做法复杂度不优，很大原因是相邻区间改变时的信息变化没有利用好。 比如k=3，序列为 5 2 4 1 3。 处理区间[1,3]时考虑的元素为 5 2 4，而处理区间[2,4]时为2 4 1。 我们发现区间移动的时候，去掉一个 5，加入一个 1，中间的 2 4 还是不变的。

k=3，序列为 5 2 4 1 3。 显然，2 肯定不会成为答案。 对于 5 而言，它在区间[1,3]里是答案。当区间向后移动变为[2,4]时，5 就不在区间内了，自然不会成为答案。而对于 4 而言，它在区间[1,3]内不是答案，但在[2,4]内，唯一比它大的数 5 走了，它就成为了答案。

相似的，我们可以考虑维护每个区间的“候选答案”。这些候选答案或许不是当前区间的答案，但在之后的区间里可能成为答案。 候选答案有哪些仅基于当前区间进行判断，与序列之后长什么样无关。 当然，当前区间的答案也在“候选答案”里。 不难证明，这些“候选答案”按下标排列后数值是单调递减的。 当加入一个新数时，它一定会成为候选答案。而区间向右移动时，旧的候选答案可能会因为下标不在区间内而被踢出。 这个结构非常队列。 因此就能顺理成章的得到做法。

我们用队列维护当前区间里的“候选答案”。按下标从小到大加入每个元素。 加入一个元素时，将队列里所有小于它的元素全移出队列。 移动到下一个区间时，加入新增的元素。同时如果队首元素的下标不在区间内，那么把队首移出队列。 每个区间的答案即为此时队首元素的值。 初始时顺次加入 a_1…a_k。 根据加入元素的方式，每次加入后，该元素一定小于队列里剩余元素。因此，队列里元素是单调递减的。 每个元素最多被加入、移出队列各一次，复杂度O(n)。

AC代码
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. const long long N=20001000;
  4. long long q[N],head=1,tail;
  5. long long n,k,a[N];
  6. int main(){
  7. 	ios::sync_with_stdio(0);
  8. 	cin.tie(0);cout.tie(0);
  9. 	cin>>n>>k;
  10. 	for(long long i=1;i<=n;i++)cin>>a[i];
  11. 	for(long long i=1;i<k;i++){
  12. 		while(head<=tail&&a[q[tail]]>=a[i])tail--;
  13. 		q[++tail]=i;
  14. 	}
  15. 	for(long long i=k;i<=n;i++){
  16. 		while(head<=tail&&a[q[tail]]>=a[i])tail--;
  17. 		q[++tail]=i;
  18. 		while(q[head]<i-k+1)head++;
  19. 		cout<<a[q[head]]<<" ";
  20. 	}
  21. 	cout<<endl;
  22. 	head=1;
  23. 	tail=0;
  24. 	for(long long i=1;i<k;i++){
  25. 		while(head<=tail&&a[q[tail]]<=a[i])tail--;
  26. 		q[++tail]=i;
  27. 	}
  28. 	for(long long i=k;i<=n;i++){
  29. 		while(head<=tail&&a[q[tail]]<=a[i])tail--;
  30. 		q[++tail]=i;
  31. 		while(q[head]<i-k+1)head++;
  32. 		cout<<a[q[head]]<<" ";
  33. 	}
  34. 	cout<<endl;
  35. 	return 0;
  36. }

 （2）P2216 [HAOI2007] 理想的正方形

题目传送门

格式化题面

给定一个 n×m 的矩阵 a 和正整数 k。你需要选出一个 k×k 的子矩阵， 使得其中最大值与最小值的差最小。求这个值。 k≤n,m≤1000,0≤a_i,j≤10^9。

思路

这题其实就是把上一道题丢到矩阵上来了。 考虑枚举每个矩阵，求出枚举矩阵的最大值和最小值。 那么就从左到右、从上到下的枚举每个矩阵，仿照上一题做法。 但有两个问题。 第一个是每次移动时改变的元素不是 1 个，而是 k 个。 第二个是当一行矩阵枚举完后，下一个矩阵的左上角会是下一行第一列。此时元素变化情况是很多的。

第一个问题很好解决。 虽然加入了 k 个元素，但这 k 个元素被从队首踢出的时间也是一样的。因此提前处理出这 k 个元素的最大和最小值，加入时就可以只加入一个值了。 不难发现处理这步实际上就是对每一列问，任意相邻 k 个元素中最大值和最小值。 这就直接回到例题了，直接单调队列就能做。 第二个问题更简单了。 我们的单调队列中元素始终不超过 k 个。 换行最多发生 n 次，因此暴力清空单调队列再重新加入新的值就可以了。 复杂度 O(nm)。

AC代码
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. const int N=1010;
  4. int tail1,tail2,head1,head2,n,m,k,mx[N][N],mn[N][N];
  5. int a[N][N],q1[N],q2[N];
  6. int main(){
  7. 	ios::sync_with_stdio(0);
  8. 	cin.tie(0);cout.tie(0);
  9. 	cin>>n>>m>>k;
  10. 	for(int i=1;i<=n;i++)
  11. 		for(int j=1;j<=m;j++)
  12. 			cin>>a[i][j];
  13. 	for(int j=1;j<=m;j++){
  14. 		head1=head2=1;tail1=tail2=0;
  15. 		for(int i=1;i<k;i++){
  16. 			while(head1<=tail1&&a[q1[tail1]][j]<=a[i][j])tail1--;
  17. 			while(head2<=tail2&&a[q2[tail2]][j]>=a[i][j])tail2--;
  18. 			q1[++tail1]=i;
  19. 			q2[++tail2]=i;
  20. 		}
  21. 		for(int i=k;i<=n;i++){
  22. 			while(head1<=tail1&&a[q1[tail1]][j]<=a[i][j])tail1--;
  23. 			while(head2<=tail2&&a[q2[tail2]][j]>=a[i][j])tail2--;
  24. 			q1[++tail1]=i;
  25. 			q2[++tail2]=i;
  26. 			if(q1[head1]<=i-k)head1++;
  27. 			if(q2[head2]<=i-k)head2++;
  28. 			mx[i-k+1][j]=a[q1[head1]][j];
  29. 			mn[i-k+1][j]=a[q2[head2]][j];
  30. 		}
  31. 	}
  32. 	int res=1e9+7;
  33. 	for(int i=1;i+k-1<=n;i++){
  34. 		head1=head2=1;tail1=tail2=0;
  35. 		for(int j=1;j<k;j++){
  36. 			while(head1<=tail1&&mx[i][q1[tail1]]<=mx[i][j])tail1--;
  37. 			while(head2<=tail2&&mn[i][q2[tail2]]>=mn[i][j])tail2--;
  38. 			q1[++tail1]=j;
  39. 			q2[++tail2]=j;
  40. 		}
  41. 		for(int j=k;j<=m;j++){
  42. 			while(head1<=tail1&&mx[i][q1[tail1]]<=mx[i][j])tail1--;
  43. 			while(head2<=tail2&&mn[i][q2[tail2]]>=mn[i][j])tail2--;
  44. 			q1[++tail1]=j;
  45. 			q2[++tail2]=j;
  46. 			if(q1[head1]<=j-k)head1++;
  47. 			if(q2[head2]<=j-k)head2++;
  48. 			int tmp=mx[i][q1[head1]]-mn[i][q2[head2]];
  49. 			res=min(res,tmp);
  50. 		}
  51. 	}
  52. 	cout<<res<<endl;
  53. }

（3）P2627 [USACO11OPEN] Mowing the Lawn G

题目传送门

格式化题面

给定长为 n 的序列 a_1…a_n，和正整数 k。你需要从序列里选出若干个数，使得选出数的和最大。 要求不能选择超过 k 个下标连续的数。 k≤n≤10^6，数字大小在 int 范围内。

思路

一道相当经典的单调队列优化 dp。 很容易列出一个二维 dp。 dp[i][j] 表示选完前 i 个数，目前已经连续选了 j 个数，和的最大值。转移时考虑新的数选或不选即可。 显然时空复杂度都是爆炸的。 考虑进行优化。 首先 dp 的状态数就是平方级别的，先考虑如何压掉状态数。

正着不好做就反着做。 按选什么考虑是没有出路的。很难规避掉最多连续选 k 个的限制。 因此不妨从不选什么的角度 dp。 dp_i 表示不选第 i 个数，前 i 个数里选出数之和最大值。 由于第 n 个数不能确定选与不选，我们在序列最后添加一个 a_n+1=0，答案就是 dp_n+1。

枚举上一个不选的点的位置，这样就相当于每次连续的选出一段区间。 求出前缀和以快速得到区间的元素和。 可得到转移式 dp_i=max （i−k−1≤j<i）(dp_j+sum_i−1−sum_j)。 对于一个固定的 i，sum_i−1 也是固定的，将其分离出来。  dp_i=max（i−k−1≤j<i）(dp_j−sum_j) +sum_i−1。 max 里所求的是一段区间的最值。i 增大的时候相应区间也在右移，因此可以直接用单调队列维护。 复杂度 O(n)。

AC代码
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. const int N=1e6+10;
  4. int n,k,a[N],q[N],head,tail;
  5. long long dp[N],sum[N];
  6. long long val(int x){
  7. 	return dp[x]-sum[x];
  8. }
  9. int main(){
  10. 	ios::sync_with_stdio(0);
  11. 	cin.tie(0);cout.tie(0);
  12. 	cin>>n>>k;
  13. 	for(int i=1;i<=n;i++)cin>>a[i];
  14. 	n++;
  15. 	for(int i=1;i<=n;i++)sum[i]=sum[i-1]+a[i];
  16. 	head=tail=1;
  17. 	for(int i=1;i<=n;i++){
  18. 		if(q[head]<=i-k-2)head++;
  19. 		dp[i]=val(q[head])+sum[i-1];
  20. 		while(head<=tail&&val(q[tail])<=val(i))tail--;
  21. 		q[++tail]=i;
  22. 	}
  23. 	cout<<dp[n]<<endl;
  24. }

（4）P2569 [SCOI2010] 股票交易

题目传送门

格式化题面

有一支股票，接下来 n 天里，买入价 ai，至多买入 bi 个，卖出价为 ci，至多卖出 di 个。 同一天只能在买入或卖出中选择一项。要求手里至多持有 K 个股票，且相邻两次交易至少间隔 W 天。 问最大收益。 n,K,W≤2000，其余数在 1000 以内。

思路

一眼 dp。 Dp[i][j] 表示 i 天后拥有 j 张股票，最大收益。 转移分四类。 手里没东西，直接买入：dp[i][j]=-a[i]*j。 不买不卖，直接继承上一天。 在之前某天基础上买入。 在之前某天基础上卖出。 发现对于前两种情况，直接平方转移即可。对后两种情况，直接枚举肯定复杂度爆炸。

结论：后两种情况的天数转移点，是当天之前第一个可交易的日子。

因为情况 2 把更往前的最优解都推到了那一天。 现在是一个三次的转移，思考如何优化掉最后一维。 我们以买入为例，卖出是类似的。 dp_i,j=max(dp_p,k−(j−k)×a_i) 。 按下标分离，a 是定系数，因此直接单调队列维护即可。

AC代码
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. const int N=2010;
  4. int n,m,ap,bp,as,bs,w,ans,f[N][N],l,r,q[N];
  5. int main(){
  6. 	ios::sync_with_stdio(0);
  7. 	cin.tie(0);cout.tie(0);
  8. 	cin>>n>>m>>w;
  9. 	memset(f,128,sizeof(f));
  10. 	for(int i=1;i<=n;i++){
  11. 		cin>>ap>>bp>>as>>bs;
  12. 		for(int j=0;j<=as;j++)f[i][j]=-1*j*ap;
  13. 		for(int j=0;j<=m;j++)f[i][j]=max(f[i][j],f[i-1][j]);
  14. 		if(i<=w)continue;
  15. 		l=1,r=0;
  16. 		for(int j=0;j<=m;j++){
  17. 			while(l<=r&&q[l]<j-as)l++;
  18. 			while(l<=r&&f[i-w-1][q[r]]+q[r]*ap<=f[i-w-1][j]+j*ap)r--;
  19. 			q[++r]=j;
  20. 			if(l<=r)f[i][j]=max(f[i][j],f[i-w-1][q[l]]+q[l]*ap-j*ap);
  21. 		}
  22. 		l = 1 , r = 0; 
  23.         for(int j = m ; j >= 0 ; j--){
  24.             while(l<=r&&q[l]>j+bs)l++; 
  25.             while(l<=r&&f[i-w-1][q[r]]+q[r]*bp<=f[i-w-1][j]+j*bp)r--; 
  26.             q[++r] = j; 
  27.             if(l <= r)f[i][j] = max(f[i][j] , f[i - w - 1][q[l]] + q[l] * bp - j * bp); 
  28.         }
  29. 	}
  30. 	for(int i=0;i<=m;i++)ans=max(ans,f[n][i]);
  31. 	cout<<ans<<endl;
  32. }

 单调栈

既然讲了单调队列，那就顺理成章的看看单调栈吧。 和单调队列一样，单调栈也要求栈里的元素单调。 单调栈的结构和单调队列非常相似，但功能差别比较大。 单调栈的应用大概分两类。 一类是在单调栈的建立过程中，通过出入栈关系获取需要的信息。 另一类是先建好单调栈，通过其中的数据获取需要的信息。 还是先看点例题吧。

例题讲解

（1）P5788 【模板】单调栈

题目传送门

格式化题面

给定长为 n 的序列 a。 定义一个区间的价值为区间最小值乘以区间长度。 求最大价值。 n≤10^6,0≤a≤10^9。

思路

不妨枚举最小值是谁，然后找到最长的区间，使得这个数是最小值。 等价于问，这个数左边和右边，第一个比它大的数分别是谁。 这个是很经典的单调栈的工作。

把 a_1…a_n 顺次插入单调栈里。 第一个数插入时，栈里没有元素，直接插入即可。第一个数左边也不可能有数比它大。 之后每次插入一个数时，不断弹出栈顶小于该数的数。这些数右边第一个比它大的数就是我们新插入的数字。 如此重复直到遇到一个比它大的数。这个数就是新插入的数字左边，第一个比它大的数。 所有数插入后，栈里剩下的数字在右边都没有更大的数。 还是比较显然的。

注意栈用完一次要初始化*_*

AC代码
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. const int N=3e7+10;
  4. int n,a[N],stk[2*N],ans[N],top;
  5. int main(){
  6. 	ios::sync_with_stdio(0);
  7. 	cin.tie(0);cout.tie(0);
  8. 	cin>>n;
  9. 	for(int i=1;i<=n;i++)cin>>a[i];
  10. 	for(int i=n;i>=1;i--){
  11. 		while(top&&a[stk[top]]<=a[i])top--;
  12. 		ans[i]=stk[top];
  13. 		stk[++top]=i; 
  14. 	}
  15. 	for(int i=1;i<=n;i++)cout<<ans[i]<<" ";
  16. }

优先队列

以下说的堆都指二叉堆。 优先队列不是队列，而是堆。 堆是一棵完全二叉树，每个节点上有一个权值。大根堆每个节点的权值大于它的左右儿子，小根堆则相反。 大根堆的根节点是堆中元素的最大值，小根堆同理。 堆支持如下几种操作。 加入一个元素、查询根节点元素、删除根节点元素。 我们看看堆是怎么实现这些功能的。 以大根堆为例。

实现

加入元素

规定堆中，所有节点从上往下、从左往右编号顺次为 1 到 n 。 新建 n+1 号节点，权值为该元素的权值。 不断将该节点与其父亲比较，若大于父亲，则与父节点交换。

删除元素

将根节点元素与最后一个节点的元素交换，然后直接删除。 这样就变成一个有 n-1 个元素的堆，但是堆顶不满足条件。 不断把堆顶元素与左右儿子中较大的交换，直到该元素大于其左右儿子或交换到叶子节点。 如何删除一个非堆顶元素？

交换依然可行，但有些更简洁的做法。 堆只能查询堆顶元素，所以给待删除元素打上一个删除标记。 当待删除元素成为堆顶时，直接删除即可。 堆是完全二叉树构造，因此对于加入和删除操作，每次操作复杂度不超过 O(logn)，n 是堆中元素个数。

例题讲解

（1）P3378 【模板】堆

题目传送门

思路

模拟堆

注意数据范围*_*

AC代码
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. const int N=1000010;
  4. int m,n;
  5. int h[N],siz,ph[N],hp[N];
  6. void heap_swap(int a,int b){
  7. 	swap(ph[hp[a]],ph[hp[b]]);
  8. 	swap(hp[a],hp[b]);
  9. 	swap(h[a],h[b]);
  10. }
  11. void down(int u){
  12. 	int t=u;
  13. 	if(u*2<=siz&&h[u*2]<h[t])t=u*2;
  14. 	if(u*2+1<=siz&&h[u*2+1]<h[t])t=u*2+1;
  15. 	if(u!=t){
  16. 		heap_swap(u,t);
  17. 		down(t);
  18. 	}
  19. }
  20. void up(int u){
  21. 	while(u/2&&h[u/2]>h[u]){
  22. 		heap_swap(u/2,u);
  23. 		u/=2;
  24. 	}
  25. }
  26. int main(){
  27. 	scanf("%d",&n);
  28. 	for(int i=1;i<=n;i++){
  29. 		char o[10];
  30. 		int k,x;
  31. 		scanf("%s",o);
  32. 		if(o[0]=='1'){
  33. 			scanf("%d",&x);
  34. 			siz++;
  35. 			m++;
  36. 			ph[m]=siz;
  37. 			hp[siz]=m;
  38. 			h[siz]=x;
  39. 			up(siz);
  40. 		}
  41. 		else if(o[0]=='2'){
  42. 			printf("%d\n",h[1]);
  43. 		}
  44. 		else{
  45. 			heap_swap(1,siz);
  46. 			siz--;
  47. 			down(1);
  48. 		}
  49. 	}
  50. 	return 0;
  51. }
  52.

 （2）P1168中位数

题目传送门

格式化题面

给定长为 n 的序列 a，保证 n 是奇数。 求前 1,3,5,…,n 个数的中位数。 n≤5×10^5,0≤a_i≤10^9。

思路

经典的对顶堆题目。 我们开两个堆，一个大根堆和一个小根堆。 大根堆内元素均小于小根堆内元素。 加入一个数时，如果其小于大根堆堆顶则丢到大根堆里，否则丢给小根堆。 假设两个堆内总共有 k 个数，那么规定大根堆的“容量”是 k/2 下取整，小根堆就是 k 减去大根堆容量。 如果有一个堆数字个数超出其容量，则不断弹出堆顶给另一个堆。 答案即为小根堆堆顶，复杂度 O(nlogn)。

AC代码
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. int read(){//读入优化
  4. 	int x=0;bool f=0;char c=getchar();
  5. 	while (c<'0'||c>'9'){if (c=='-')f=1;c=getchar();}
  6. 	while (c>='0'&&c<='9'){x=(x<<1)+(x<<3)+(c^48);c=getchar();}
  7. 	return f?-x:x;
  8. }
  9. priority_queue<int,vector<int> > q1;//大根堆
  10. priority_queue<int,vector<int>,greater<int> > q2;//小根堆
  11. int main(){
  12. 	int n=read();q1.push(read());
  13. 	cout<<q1.top()<<endl; 
  14. 	for (int i=2;i<=n;i++){
  15. 		int input=read();//等同于cin>>input
  16. 		if (input>q1.top()) q2.push(input);
  17. 			else q1.push(input);
  18. 		while (abs(q1.size()-q2.size())>1)
  19. 			if (q1.size()>q2.size()){q2.push(q1.top());q1.pop();}
  20. 				else{q1.push(q2.top());q2.pop();}
  21. 		if (i%2) cout<<(q1.size()>q2.size()?q1.top():q2.top())<<endl;
  22. 	}
  23. 	return 0;
  24. }

这是我的第十篇文章，如有纰漏也请各位大佬指正

辛苦创作不易，还望看官点赞收藏打赏，后续还会更新新的内容。

本文内容由网友自发贡献，转载请注明出处：【wpsshop博客】
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号