算法刷题笔记 滑动窗口（C++实现，非常详细）

题目描述

• 给定一个大小为n ≤ 10^6的数组。
• 有一个大小为k的滑动窗口，它从数组的最左边移动到最右边。
• 你只能在窗口中看到k个数字。
• 每次滑动窗口向右移动一个位置。以下是一个例子：
  • 该数组为 [1 3 -1 -3 5 3 6 7]，k为3。
    
• 你的任务是确定滑动窗口位于每个位置时，窗口中的最大值和最小值。

输入格式

• 输入包含两行。
• 第一行包含两个整数n和k，分别代表数组长度和滑动窗口的长度。
• 第二行有n个整数，代表数组的具体数值。同行数据之间用空格隔开。

输出格式

• 输出包含两个。
• 第一行输出，从左至右，每个位置滑动窗口中的最小值。
• 第二行输出，从左至右，每个位置滑动窗口中的最大值。

基本思路

这道题是单调队列系列题目的最基础的模板题，但是对于像我这样的初学者来说仍然难度较大，因此我将对该题的思路进行详细解析。

• 算法题的核心是将一个有直观、暴力的思路的算法优化为一个逻辑上更加复杂，但是时间和空间上更占优势的算法。那么，对于这道题，我们就需要首先思考蛮力算法的求解步骤是什么。本题的蛮力算法非常直观，就是一个简单的双重遍历。例如，对于数组[1 3 -1 -3]，并假设窗口大小为3，那么我们就从数组的第一个元素开始遍历，向右滑动窗口，每次遍历到的数组元素作为窗口的左端点。以这个例子为例，可以得到两个窗口[1 3 -1]和[3 -1 -3]，再分别从这两个窗口中找出最大值和最小值即可。代码实现上，可以大致如下：

#include <cstdio>
#include <vector>
using namespace std;

// 本例子中n为4，k为3，假设原始数组为arr，本例子以最大值为例
for(int i = 0; i < n - k + 1; ++ i)
{
    // 使用一个向量表示当前窗口，并向该窗口中添加元素
    vector<int> window;
    for(int j = i; i < i + k; ++ j) window.push_back(arr[j]);
    // 查找该向量中的最大值并输出
    int max = window[0];
    for(int j = 1; j < window.size(); ++ j) if(window[j] > max) max = window[j];
    printf("%d ", max);
}

• 但是，我们仔细考虑一下，这种方法存在明显的冗余性。两个相邻的滑动窗口之间，有且只有一个元素不相同，而窗口中的其他元素都是完全一样的，因此会经过多轮重复遍历，创建多个大部分元素都相同的向量，算法的时间复杂度为O(nk)。既然存在冗余元素，那么我们就需要从数据结构和算法的角度上考虑对算法进行优化。
• 直观上，我们可以发现既然相邻的两个窗口只有一个元素存在区别，即相当于下一个窗口的元素是去除了上一个窗口中的首元素，并且在后面添加了一个新元素，这就很类似于数据结构中常用的队列数据结构。因此，如果能够使用队列来代替向量，那么就可以提高算法的效率。实现代码如下：

#include <cstdio>
#include <deque>
using namespace std;

// 首先创建一个队列，并以第一个窗口中的元素进行初始化
deque<int> window;
for(int i = 0; i < k; ++ i) window.push_back(arr[i]);
// 每轮遍历队首元素出栈，并从队尾入队一个元素
for(int i = k; i < n - k + 1; ++ i)
{
    window.pop_front();
    window.push_back(arr[i]);
    // 查找当前队列中的最大值
    int max = window.front();
    for(int item : window) if(item > max) max = item;
    printf("%d ", max);
}

• 基于队列的实现代码的确能够有更高的时间效率，但是是否可以进一步优化呢？我们发现，尽管使用队列可以更加方便地创建和维护一个窗口，而不像向量那样需要每次完全重新新建一个，但是在查找最大值时，仍然需要遍历整个队列。如果我们想要继续提高效率，就必须简化查找过程，避免耗时的循环遍历，此时就应该使用单调队列进行处理。

• 仍然以[1 3 -1 -3]为例，当我们每一轮循环更新队列时，我们可以修改我们的更新策略。下面进行举例说明，以查找最大值为例。

  • 第一轮：队列初始为空，因此直接将第一个元素1放入队尾即可。
  • 第二轮：队列目前为[1]，当前遍历到的元素为3；由于3大于当前的队尾元素1，因此如果3也放入队尾后，在查找最大值的过程中，元素1一定不会成为任何一个窗口的最大值了。这是因为当元素1和元素3在同一个窗口中时，3比1大，因此最大值不可能是1；当元素1和元素3不在同一个窗口中时，只有一种可能，就是当前窗口中已经不包含1了，这是因为3在原始数组中排在1的后面，只要1在窗口中，3一定在窗口中，所以这种情况下，窗口中已经不包含有元素1，所以自然不会成为最大值。因此，可以认为队列中的1为冗余元素，可以直接将其出队。只有某个元素可能成为某个窗口的最大值时，才会被放入队尾进入队列中，而所有确定下来的冗余元素都出队。所以，在第二轮迭代中首先通过上述比较过程，让队尾的1出队，此时队列为空，则直接把当前元素3放入队列中。
  • 第三轮：队列目前为[3]，当前遍历到的元素是-1。由于队尾元素3比-1更大，因此直接将-1入队放入队尾即可，这是因为3会在-1之前从队头离开队列，此时-1就有可能成为某个窗口的最大值元素。
  • 第四轮：和第三轮类似，队列目前是[3 -1]，当前遍历到的元素是-3。由于队尾元素-1比-3更大，因此直接将-3放入队尾。

• 那么，应该如何确定何时要将队头元素出队呢？队头元素出队表示该元素已经不在当前的窗口中，最简单的处理方法就是用另一个队列记录所有队列中的元素在数组中的下标，并在每一轮的遍历过程中，通过下标判定队首元素是否在窗口中即可。下标队列和元素队列中的元素应该是一一对应的，需要同时添加和同时删除。

实现代码

#include <cstdio>
#include <deque>
using namespace std;

const int N = 1e6 + 10;
int arr[N];

int main(void)
{
    int n, k;
    scanf("%d%d", &n, &k);
    for(int i = 0; i < n; ++ i) scanf("%d", &arr[i]);
    deque<int> q;
    deque<int> index;
    // 最小值部分
    for(int i = 0; i < n; ++ i)
    {
        while(!q.empty() && q.back() >= arr[i])
        {
            q.pop_back();
            index.pop_back();
        }
        q.push_back(arr[i]);
        index.push_back(i);
        if(i >= k && i - k == index.front())
        {
            q.pop_front();
            index.pop_front();
        }
        if(i > k - 2) printf("%d ", q.front());
    }
    // 清空两个队列，对称地求解最大值
    q.clear();
    index.clear();
    printf("\n");
    for(int i = 0; i < n; ++ i)
    {
        while(!q.empty() && q.back() <= arr[i])
        {
            q.pop_back();
            index.pop_back();
        }
        q.push_back(arr[i]);
        index.push_back(i);
        if(i >= k && i - k == index.front())
        {
            q.pop_front();
            index.pop_front();
        }
        if(i > k - 2) printf("%d ", q.front());
    }
    return 0;
}