算法设计-单调队列-Toy模板网

这篇具有很好参考价值的文章主要介绍了算法设计-单调队列。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

这个东西我弄得还不是很明白，所以先放一篇博客：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;