概念
单调队列是一个满足内部单调递增或单调递减的数据结构。
实质
单调队列是一个 双端队列。
特点
- 从队尾入列,队首或队尾出列。
- 队列中元素大小必须是 单调 的。
- 队列中的元素对应在原来列表中的顺序必须是 单调递增 的。
作用
维护区间最值或降低 维数来达到减少空间及时间的目的。
例题
第一思路暴力,两个 循环就搞定了,但这样的算法时间复杂度为
,肯定会超时。所以要优化,这就用上了单调队列。
以求最大值为例(最小值同理),我们可以这样维护队列的值:
- 维护队首:如果队首元素下标在当前下标的
个之前,弹出队首。
- 维护队尾:比较当前元素与队尾元素的大小,若当前元素更优,弹出队尾元素,直到可以满足队列单调性后加入当前元素。因为如果对于两个元素
,
且
,那么窗口在右端滑到
之后,
再也不可能成为最大值。
对于这道题,我们模拟窗口右移的过程,每右移一个单位,就将若干个元素踢出 队首或队尾 ,并将新的元素加入 队尾。
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
int n,k,f[1000100];
int w[1000100],v[1000100];
void get_max()//维护最大值
{
printf("\n");
memset(w,0,sizeof(w));
memset(v,0,sizeof(v));
int head=1,tail=0;
for(int i=1;i<=n;i++){
while(head<=tail&&w[tail]<f[i]) tail--;
w[++tail]=f[i];//储存值
v[tail]=i;//储存位置
while(v[head]<=i-k&&head<tail) head++;
if(i>=k) printf("%d ",w[head]);
}
}
void get_min()//维护最小值
{
int head=1,tail=0;
for(int i=1;i<=n;i++){
while(head<=tail&&w[tail]>f[i]) tail--;
w[++tail]=f[i];
v[tail]=i;
while(v[head]<=i-k&&head<tail) head++;
if(i>=k) printf("%d ",w[head]);
}
}
int main()
{
scanf("%d%d",&n,&k);
for(int i=1;i<=n;i++)
scanf("%d",&f[i]);
get_min();
get_max();
return 0;//撒花
}
是不是很简单
那么进入下一个话题:
单调队列优化DP
在讲之前,先普及一下知识:
1D动态规划
指的是状态数为 ,每一个状态决策量为
的动态规划方程,这样的方程直接暴力求解的时间复杂度为
。(基本会
)
这里只讲单调队列优化1D动态规划:
在1D动态规划中,有一种 ,转移方程一般为:
dp[i]=min(dp[i],dp[j]+f[i][j])
其中 ,
与
的序列单调不减。
也可以写成
,方法是一样的。
这种 可以用单调队列分
步进行优化:
- 将所有小于
的
全部踢队。
- 用队首
为
赋值,队首
要变化。
- 将新元素
加入队尾
,队尾
也要变化。
- 维护单调队列。
基本内容就是这些,其实动脑推出 方程式就行了。
说得简单
版权声明:本文为Da_un原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。