滑动窗口的最大值

题目描述

核心思路

这种滑动窗口的题都可以考虑用单调队列来求解。

单调队列：队列内的元素是单调的，递增或者递减

本题采用单调队列来存储当前窗口内单调递减的元素，并且队头是窗口内的最大值，队尾是窗口内的尾元素，也就是说，队列从队头到队尾对应窗口内从最大值到尾元素的一个子序列。

• 队头出队：当队头的元素从窗口中滑出时，队头元素出队head++。比如原序列24 【58 54 3】 15 13，队列中队头元素是58，然后窗口向右滑动一个，变成了24 58 【54 3 15】 13，那么此时原来的队头元素58也必须出队了，因为我们只考虑窗口内的元素，而不考虑窗口外的元素。因此如果队列中的队头元素在原序列中如果已经脱离了窗口，则要出头。

• 队尾入队：当新元素滑入窗口时，要把新元素从队尾插入，分为两种情况：
  • 直接再队尾元素后面插入新元素：如果新元素小于队尾元素，那就直接把这个新元素从队尾插入，tail++，这样可以保证队列单调递减，因为这个新元素可能在当队列中它前面的最大值出队后成为最大值。如下图所示，原来队列中队尾元素是6，现在来了一个新元素4，由于新元素4小于队尾元素6，因此可以加入队列。

  

  • 先删除队尾元素再加入新元素：如果新元素大于等于队尾元素，那就删除队尾元素(因为此时队尾元素不可能成为队列中的最大值了)，删除方法是tail–，即从队尾出队。循环删除，直到队空或者遇到队列中的某个队尾元素大于新元素时，那么就转变成了第一种，将这个新元素插入到这个队尾元素后面即可。

    如下图所示，原来队列中有6、4，来了新元素9，由于新元素9大于队尾元素4，所以4出队，继续，由于新元素9大于队尾元素6，所以6出队，此时队列为空，那么就直接将这个新元素9放入到队列中即可。

通过上面这么做，每次都能从队头取得窗口中的最大值。

分析步骤如下：

• 当i=1时，窗口内只有一个元素2，因此队列中也只有一个元素2，如下图

• 当i=2时，窗口内有两个元素2、6，此时队列中的元素是6，如下图

• 当i=3时，窗口内有三个元素2、6、4，此时队列中的元素是6、4，如下图

  

• 当i=4时，窗口右移一个，那么新的窗口内有三个元素6、4、9，此时队列中的元素是9，如下图

• 当i=5时，窗口右移一个，那么新的窗口内有三个元素4、9、8，此时队列中的元素是9、8，如下图

• 当i=6时，窗口右移一个，那么新的窗口内有三个元素9、8、5，此时队列中的元素是9、8、5，如下图

• 当i=7时，窗口右移一个，原来队列中的队头元素9在原序列中已经滑出了窗口，因此此时队列中的9也必须出队了，那么新的窗口内有三个元素8、5、5，此时队列中的元素是8、5，如下图

• 当i=8时，窗口右移一个，原来队列中的队头元素8在原序列中已经滑出了窗口，因此此时队列中的8也必须出队了，那么新的窗口内有三个元素5、5、2，此时队列中的元素是5、2，如下图

每次操作完成后，队头元素都是窗口内的最大值。

经过模拟可以发现，指向完

q[++tt]=i

后，那么此时

q[tt]

的值就是 i i i的值，而 i i i它指向就是当前窗口的右端点，那么也就是说，

q[tt]

也是指向当前窗口的右端点。

上面我们模拟时，队列中存储的是元素，但是如果我们让队列存储的是元素，由于可能有重复元素，那么是很难判断队头元素该什么时候才能出队。但是如果我们让队列存储的是元素的下标，比如此时队头元素的下标为 x x x，窗口最后一个元素的下标是 i i i，设窗口大小为m，那么当 i − x > m i-x>m i−x>m时，则说明我们的窗口右移了一个，那么原来队列中的队头元素就不在窗口中了，因此这样就可以说明队头出队了。

由于每个元素最多入队和出队各一次，应该该算法的时间复杂度是 O ( n ) O(n) O(n)。

求窗口内的最大值代码如下：

int hh=0,tt=-1;
for(int i=1;i<=n;i++)//遍历序列
{
    //当队列不空，并且如果q[hh]不在窗口[i-m+1,i]中，则队头出队
    if(hh<=tt&&q[hh]<i-m+1)
        hh++;
    //当队头元素不为空，并且新来的元素a[i]大于等于队尾元素时，队尾元素出队
    while(hh<=tt&&a[i]>=a[q[tt]])
        tt--;
    //到这里说明这个新元素可以直接加入队列中，下标入队
    q[++tt]=i;
    //当达到窗口的大小m时才能输出，比如窗口大小m=3,那么刚开始窗口为0，1，2时，都不满足窗口的大小，不能输出
    //这里如果i是从1开始取，那么就要写成i>m-1;如果i是从0开始取，那么就要写成i>=m-1
    if(i>m-1)//其实这里写成i>=m也是可以的
        printf("%d ",a[q[hh]]);
}
           

STL中的双端队列deque也可以代替单调队列：

deque<int>q;
for(int i=1;i<=n;i++)
{
    if(!q.empty()&&q.front()<i-m+1)
        q.pop_front();
    while(!q.empty()&&a[i]>=a[q.back()])
        q.pop_back();
    q.push_back(i);
    if(i>m-1)
        printf("%d ",a[q.front()]);
}
           

对于如果要求窗口内的最小值，那么其实我们可以让这个单调队列是递增的，那么此时队头元素就是最小值。代码如下：

int hh=0,tt=-1;
for(int i=1;i<=n;i++)
{
    if(hh<=tt&&q[hh]<i-m+1)
        hh++;
    while(hh<=tt&&a[i]<=a[q[tt]])
        tt--;
    if(i>m-1)
        printf("%d ",a[q[hh]]);
}