单调队列
单调队列是一种数据结构。
随着区间的向右滑动,区间[i,j)变为[i+1,j+1);
如果a[i]是不是原区间最大值,那么新区间的最大值就是max(q.front(),a[j]);
如果a[i]是原区间最大值,那么新区间最大值就是max(原区间第二大值,a[j]);
单调队列的队首始终是一个区间内的最大值;
队列的第二个元素是要满足位置在队首元素的右边,而且是在区间中第二大的那个点。
当队首元素滑出区间的范围的时候,队列执行q.pop_front()操作,将队首元素弹出。
当队首元素弹出之后,队列中的第二个元素自动变成新的队首,在原来区间中的第二大元素也变成了第一大元素。
也就是说 单调队列中元素的大小是单调的,而且元素的位置也是单调递增的。
。。。。。