[Acwing] 154. 滑动窗口 单调队列

前言

hh总算是理解了

传送门 :

思路

朴素算法的分析 :

显然我们可以对于每一个区间都进行一遍找最大最小值,

时间复杂度 O ( n ∗ k ) O(n*k) O(n∗k),在 k k k大的情况下,显然是会 T L E TLE TLE的,而且我们也不难发现,对于

除了开头 k − 1 k-1 k−1和结尾 k − 1 k-1 k−1个数之外,其他数都进行了 k k k次 比较

这里我们可以采用单调队列优化 :

队列的性质 : 后进先出

对于入队操作,我们考虑 :

如果当前一个数需要进入队列内,若这个数比先进队的数大 , 那么显然 前面的数不可能是

我们需要统计的最大值,一定先出列,并且我们将这个数弹入队尾,这样子就可以确保,每

次到了统计答案的区间的时候,队头一定是最大的那个

因为每一个数,入队出队一次,所以时间复杂度变为 O ( n ) O(n) O(n)

CODE

const int N  = 1e6+10;
int q[N],a[N];
int n,k;
void getmin(){
		int  hh = 0 ,tt = -1;
	//定义为空队列
	
	for(int i=1;i