【题解】滑动窗口（单调队列）

题目描述：

输入：

输入包含两行。

第一行包含两个整数 n">n 和 k">k，分别代表数组长度和滑动窗口的长度。

第二行有 n">n 个整数，代表数组的具体数值。

同行数据之间用空格隔开。

输出：

输出包含两个。

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

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

样例:

思考理解：

使用数组实现的单调队列解决。维护两个队列，一个最大值、一个最小值。两个操作分开做，过程几乎一样。

将删除冗余元素，维护一个严格单调的队列，则可以用O(1)时间从队头/队尾取出最值。

以最大值为例，我们需要保证队列内部递减，则队头即所求最大值，过程如下：

1. 队头出队。当队头元素从窗口滑出时，队头元素出队
2. 队尾入队。a.直接入队：当新元素小于队尾元素时，直接插入队尾。b.先删后插：如果新元素大于对位元素，就删除队尾元素，循环删除直到队空或者遇到一个比自身大的元素。两种删除方式都是为了保持队列内部递减（最小值则保持内部递增）
3. 满足条件就输出结果。

需要注意的是：

• 一定先让新元素入队再检查是否输出（即先2后3），因为要输出的结果可能是新插入的元素
• 队列中存的是原数组的下标，取值时要再套一层，a[ q[ ] ]；
• 用 scanf 和 printf 提高读入数据和输出数据的效率

代码

# include 
using namespace std;
const int N = 1000010;
int a[N], q[N], hh, tt = -1;

int main()
{
    int n, k;
    cin >> n >> k;
    for (int i = 0; i < n; ++ i)
    {
        scanf("%d", &a[i]);
        //队头出队
        if (i - k + 1 > q[hh]) ++ hh;
        //循环删除直至满足队列严格单调
        while (hh <= tt && a[i] <= a[q[tt]]) -- tt;
        //插入当前新元素
        q[++ tt] = i;
        //输出结果
        if (i + 1 >= k) printf("%d ", a[q[hh]]);
    }
    cout << endl;
    
    //同理
    hh = 0; tt = -1;
    for (int i = 0; i < n; ++ i)
    {
        if (i - k + 1 > q[hh]) ++ hh;
        while (hh <= tt && a[i] >= a[q[tt]]) -- tt;
        q[++ tt] = i;
        if (i + 1 >= k) printf("%d ", a[q[hh]]);
    }

    return 0;
}