滑动窗口

题目链接：https://www.acwing.com/problem/content/156/

题目描述

给定一个大小为 n≤106 的数组。
有一个大小为 k 的滑动窗口，它从数组的最左边移动到最右边。
你只能在窗口中看到 k 个数字。
每次滑动窗口向右移动一个位置。
你的任务是确定滑动窗口位于每个位置时，窗口中的最大值和最小值。

输入描述

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

输出描述

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

示例

输入

8 3
1 3 -1 -3 5 3 6 7

输出

-1 -3 -3 -3 3 3
3 3 5 5 6 7

分析

首先，我们可以想到滑动窗口每右移一步，我们就遍历该窗口找到其最大值最小值，时间复杂度为 $O(nk)$ 。

单调队列，则是在暴力算法的基础上挖掘问题的性质来优化算法。

下面的分析以最小值为例，最大值同理。

序列 $d$ 中的两个数，其下标分别为 $i$ 和 $j$ ，若下式同时成立：

$$\left\{\begin{array}{l} i<j \\ d_i>d_j \end{array}\right.$$

则对于已经包含 $d_j$ 的滑动窗口， $d_i$ 必不可能是最小值，且 $d_j$ 将晚于 $d_i$ 消失，所以 $d_i$ 无需考虑。

因此，对暴力算法的改良就呼之欲出了。我们维护一个队列，利用上面的性质删去一些没有必要存在的数字，使需要考虑的元素从整个滑动窗口减少，从而加速算法。

显然，队列中的元素由队头到队尾单调递增，因此该数据结构称为单调队列，队头元素即为滑动窗口的最小值。

每一个位置只会入队一次，并且最多出队一次，所以单调队列的总时间复杂度为 $O(n)$ 。

AC代码

---

#include <cstdio>
#include <deque>

using namespace std;

const int N = 1e6 + 10;
int n, k;
int a[N];
deque<int> q;
//注意，由于队头队尾都要操作，应使用双端队列

int main()
{
    scanf("%d %d", &n, &k);
    for(int i = 0; i < n; i++)
        scanf("%d", &a[i]);
    
    for(int i = 0; i < n; i++)
    {
        if(!q.empty() && i - q.front() + 1 > k)
            q.pop_front();
        while(!q.empty() && a[q.back()] >= a[i])
            q.pop_back();
        q.push_back(i);
        if(i >= k - 1)
            printf("%d ", a[q.front()]);
    }
    printf("\n");
    q.clear();
    for(int i = 0; i < n; i++)
    {
        if(!q.empty() && i - q.front() + 1 > k)
            q.pop_front();
        while(!q.empty() && a[q.back()] <= a[i])
            q.pop_back();
        q.push_back(i);
        if(i >= k - 1)
            printf("%d ", a[q.front()]);
    }
    return 0;
}