思路与算法

维护两个存下标的双端队列：最大值队列对应的数值递减，最小值队列递增。读入第i个数时，先删掉已经不在窗口内的队首，再从队尾删去被新元素支配的下标，最后加入i。窗口长度达到k后，两个队首分别给出最大值与最小值。

正确性说明

若较早的元素不优于较晚元素，且两者都在当前窗口中，较晚元素在今后所有包含较早元素的窗口里也存在，因此较早元素不会再成为唯一最优，可以删除。队首按下标过期后及时移除，剩余队列仍包含窗口的最优候选，所以每次取出的极值正确。

复杂度

每个下标在每个队列中只进出各一次，总时间 O(N)。本实现保存输入数组，空间 O(N)，两个队列最多各保存 O(K) 个下标。

易错点

输出每个窗口一行，先最大值再最小值；不是先输出所有最小值再输出所有最大值。k=1、k=n、重复值和int两端值都要正确处理。队列存下标，才能判断元素是否过期。

参考代码（C++11）

#include <bits/stdc++.h>
using namespace std;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, k;
    cin >> n >> k;
    vector<int> a(n);
    deque<int> hi, lo;
    for (int i = 0; i < n; i++) {
        cin >> a[i];
        while (!hi.empty() && hi.front() <= i - k)
            hi.pop_front();
        while (!lo.empty() && lo.front() <= i - k)
            lo.pop_front();
        while (!hi.empty() && a[hi.back()] <= a[i])
            hi.pop_back();
        while (!lo.empty() && a[lo.back()] >= a[i])
            lo.pop_back();
        hi.push_back(i);
        lo.push_back(i);
        if (i >= k - 1)
            cout << a[hi.front()] << ' ' << a[lo.front()] << '\n';
    }
}