【Week5作业 D】滑动窗口【单调队列】

题意: 现有一个长度为n的数列和一个大小为k的窗口(1<=k<=n<=1000000),窗口可以在数列上来回移动。现在要求出在窗口从左往右滑的时候,每次窗口内数的最大值和最小值分别是多少。 思路: 寻找窗口的最大值最小值,是一个局部的概念,可以使用单调队列。 如最小值(从队首到队尾单增):先装上前k-1个,如果队列不为空且要加入的元素值小于队列尾的值,则将队尾弹出,直到队尾小于要加入的元素或者队列为空为止,然后加入当前元素。 之后还剩下n-k+1个元素,对应n-k+1个窗口。i=k-1到n-1开始遍历,使用l记录当前窗口最左端元素,若最左元素不属于窗口(i-l+1>k),则