算法设计 - 单调队列

这个东西我弄得还不是很明白，所以先放一篇博客：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。感觉十分丑陋。