单调队列

作者: qwq 分类: 算法 发布时间: 2018-04-11 15:32

单调队列是一种数据结构。

随着区间的向右滑动,区间[i,j)变为[i+1,j+1);

如果a[i]是不是原区间最大值,那么新区间的最大值就是max(q.front(),a[j]);

如果a[i]是原区间最大值,那么新区间最大值就是max(原区间第二大值,a[j]);

单调队列的队首始终是一个区间内的最大值;

队列的第二个元素是要满足位置在队首元素的右边,而且是在区间中第二大的那个点。

当队首元素滑出区间的范围的时候,队列执行q.pop_front()操作,将队首元素弹出。

当队首元素弹出之后,队列中的第二个元素自动变成新的队首,在原来区间中的第二大元素也变成了第一大元素。

也就是说 单调队列中元素的大小是单调的,而且元素的位置也是单调递增的。

。。。。。

发表评论

电子邮件地址不会被公开。 必填项已用*标注