单调队列stl及手写实现,附例题

单调队列: 有单调性的队列(单调递增或递减),相比普通队列不同在于可以在队尾进行pop操作
特点: 可以快速取出最大值最小值(队首元素)
严格单调序列:a1a2a3…an,即a[i]和a[i+1]不能相等
时间复杂度: 每个元素出队入队各一次,总复杂度O(n),均摊下来每次维护队列的操作为O(1)
维护方法:
不严格单调递增为例:

  • 每次入队时与队尾元素比较,如果队列非空且小于(大于)队尾元素,就将队尾元素pop,重复上述操作直到队列为空或大于等于队尾元素,再将元素压入队尾。
STL实现方法:#includedeque

deque是双端队列,既有队列的性质也有栈的性质。
deque对象创建:dequetypename que
deque的一些成员函数:

函数名功能
push_back()队尾入队
push_front()队首入队
pop_front()队首元素出队
pop_back()队尾元素出队
empty()判断队列是否为空
front()返回队首元素
back()返回队尾元素

入队操作:

	while(!que.empty()que.back()value)que.pop_back();
	que.push_back(value);//value 为要入队的元素

如果要维护长度的话另加操作

手写实现:
#includeiostream
using namespace std;
const int MAX_N=1e4; 	//确保大小够用 
int que[MAX_N],head=0,tail=0;		//队首队尾指针,队列大小即为 tail-head 
int main()
{
	int arr[10]={135,6,4,9,7,1,6,3,8,8};
	for(int i=0;i10;i++)
	{
		if(i=3que[head]==arr[i-3])head++;	//头后移,出队 
		while(headtailque[tail-1]arr[i])tail--;	//队尾前移,出队 
		que[tail++]=arr[i];	//入队
		coutque[head]" ";
	} 
	return 0;
}
经典例题:P1440 求m区间内的最小值

题解:

#includeiostream
#includecstdio
using namespace std;
const int MAX_N=2e6+1;
int arr[MAX_N];
int que[MAX_N],head=0,tail=0; 
inline int read()
{
	int sum=0,f=1;
	char c=getchar();
	while(c'0'||c'9'){if(c=='-')f=-1;c=getchar();}
	while(c='0'c='9'){sum=(sum1)+(sum3)+c-48;c=getchar();}
	return sum*f;
}
inline void write(int x)
{
    char ch[20];
    int len=0;
    if(x0)
      {
        putchar((15)+(13)+(12)+1);
        x=~x+1;
      }
    do 
      {
        ch[len++]=x%10+(14)+(15);
        x/=10;
      }while(x0);
    for(int i=len-1;i=0;i--) 
       putchar(ch[i]);
    return ;
} 
int main()
{
	int n=read(),m=read();
	cout0endl;
	for(int i=0;in-1;i++)
	{
		arr[i]=read();
		if(i=mque[head]==arr[i-m])head++;
		while(head!=tailarr[i]que[tail-1])tail--;
		que[tail++]=arr[i];
		write(que[head]);
		putchar('\n');
	}
	return 0;
}
最新回复(0)
/jishuiIpvi987GEfO5x02923mKO0y3wQjO_2BB4_2FC8nXIXiZQU_3D4794743
8 简首页