0%

算法设计-单调队列

这个东西我弄得还不是很明白,所以先放一篇博客:https://www.cnblogs.com/I-Love-You-520/p/13454305.html

单调队列说的就是博客中提到的场景,可以说解决的是固定长度,多次查询一段的最值(其实就是slice window的意思),这种如果是朴素算法的话,因为查一段序列的最值的时间复杂度是 $O(k)$ (k 是序列长度),然后这段序列需要平移改变,所以外层有一个循环,这样复杂的就是 $O(nk)$ (如果序列长为 n )。采用单调序列的方式,可以让时间复杂度下降到 $O(n)$ 。单调队列的队头即为所求。

此外,关于这篇博客的算法,其实队列中存储的是原数组的下标,而不是原数组元素的值。当然,如果写的更好一些,可以有一个封装,如下所示

typedef long long LL;
struct monotone_queue
{//单调队列
	int head,tail,id[N];
	LL d[N];

	inline void init()
    {
        // 这种方法处理感觉有点low,只是为了判断队空与否
		head = 1,tail = 0;
	}
	//v就是入队的值,x是数组索引(下标)
	inline void push(LL v,int x)
    {   //第一个参数为dp[i][x]
		while(head <= tail && d[tail] <= v)
            tail--;
		d[++tail] = v;
		id[tail]=x;
	}
	//x是数组索引
	inline void pop(int x)
    {//弹出,指的是当范围移动的时候,要把移出范围的元素删掉
		while( head <= tail && id[head] - x >= s)
            head++;
	}
}q;

在这个代码里面,采用了两个数组,d 数组用来储存值(也就是队列功能,这个队列就是最丑陋的非循环队列),而 id 数组用来实现数组元素的移出。每次移动框,都是先插入,然后弹出。

单调队列的队头指针指向队首元素,队尾指针指向队尾元素。出队操作可以发生在队头和队尾,入队操作只能发生在队尾,判断队空用的是 head <= tail。感觉十分丑陋。