这是一篇题解笔记，这貌似被认为是一个经典题。题目链接：OpenJudge - 7:滑动窗口

题目

总时间限制: 12000ms　内存限制: 65536kB
描述
给定一个长度为n（n<=10^6）的数组。有一个大小为k的滑动窗口从数组的最左端移动到最右端。你可以看到窗口中的k个数字。窗口每次向右滑动一个数字的距离。
下面是一个例子：
数组是 [1 3 -1 -3 5 3 6 7]， k = 3。

滑动窗口

你的任务是得到滑动窗口在每个位置时的最大值和最小值。

输入
输入包括两行。
第一行包括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

想法

开始接触STL后，发现set和map真是强大好用，对这个题直接暴力用multiset模拟滑动窗口：

#include <stdio.h>
#include <iostream>
#include <vector>
#include <set>

#define IOS_SPEED std::ios::sync_with_stdio(false)

using std::cin;
using std::cout;
using std::vector;
using std::multiset;

void interface(){
    int nums, size;
    int new_num;
    vector<int> lib, min, max;
    multiset<int> window;
    IOS_SPEED;
    cin >> nums >> size;
    for(int i=0; i<nums; i++){
        cin >> new_num;
        lib.push_back(new_num);
    }
    for(int i=0; i<size; i++) window.insert(lib[i]);
    min.push_back(*window.begin()); max.push_back(*window.rbegin());
    for(int i=0; i<nums-size; i++){
        auto it = window.find(lib[i]);
        window.erase(it); window.insert(lib[i+size]);
        min.push_back(*window.begin()); max.push_back(*window.rbegin());
    }
    bool first = true;
    for(auto i: min){
        if(!first) cout << " "; first = false; cout << i;
    }
    cout << "\n";
    first = true;
    for(auto i: max){
        if(!first) cout << " "; first = false; cout << i;
    }
    cout << "\n";
    lib.clear(); window.clear(); min.clear(); max.clear();
}

int main()
{
    interface();
    return 0; 
}

由于set/multiset底层是用红黑树实现，虽然是暴力，在OpenJudge上仍然能900ms通过。但是提交到洛谷上就有一个case超过1s报TLE，那就来研究一下此题“正确”的数据结构吧！

暴力做法使用的set，每次插入新的元素必须同时删除一个旧元素，旧元素在集合中的位置又必须通过再次查找得知，这当中查找、删除两步都在重复使用之前的时间戳确定的窗内其它元素的大小信息。我们不希望重复使用这些信息，毕竟整个过程中，我们关注的只是窗口内的最值。
应该采用更加简明的数据结构来存储这些数值，且它应该保存以下两个方面的信息：(1) 元素在数集内的出现顺序，这方面较适合这里的情况的就是队列；(2) 数集内的一种层次大小结构，或者说单调结构，能够借其确保每次最大/最小值的询问都可以快速返回。这两条信息对应窗口的两个行为，一是元素的进出，二是最值的询问。
有了这些前提，就可以动手设计这道题使用的数据结构（单调队列）了，其精巧地满足了我们的需求。在这个问题里，使用的是一个双端队列。

在窗口建立（从读入第一个数到读入第size（窗口的大小）个数）和滑动的过程中，我们维护一个队列，它的行为和正常的队列一致，但是会自动淘汰那些不可能作为最小/大值询问结果的元素。以最小值为例，如果一个数出现在数的后边，但是比和都要小，那么在插入以后，这两个数就永远没有机会作为窗口的最小值输出。
要实现这一点，每当新元素要进入，我们都比较它与前一个进入的元素（当前的 back）的大小。如果新元素更小，则当前的back被淘汰，将它弹出，让下一个back与新元素比较；如果新元素更大或一路到达了的头部，由于此后这元素可能成为最小值，将它先存储在队列的末尾。
我们只需再实现窗口左侧元素的弹出功能。好的情况下，让弹出现存的第一个元素（front）即可；然而窗口左侧元素可能已经被淘汰，front未必是它。不要紧，我们换成存储元素的下标，这样就能监测的front是否该弹出了。
在整个算法中，我们做的比较几乎都是刚好必要的。每进入一个新元素，都至多需要size次比较，然而真正要这么多次比较的频率会很低（如果某次进入新元素需要size次比较，则说明窗口完全递增且新元素最小，而加入下一个元素要么会破坏这种递增，要么会花费很少的比较次数，即不会总要比较size次），因此这个算法的性能应当是很好的。（2022/7/6 Edit：实际上直接可以看出均摊的时间复杂度为 。）

实际情况也是如此。采用单调队列后（用std::list实现），在OpenJudge上300ms通过：

#include <stdio.h>
#include <iostream>
#include <vector>
#include <list>

#define IOS_SPEED std::ios::sync_with_stdio(false)

using std::cin;
using std::cout;
using std::vector;
using std::list;

void interface(){
    int nums, size;
    int new_num;
    vector<int> lib;
    list<int> min, max, min_answ, max_answ;
    IOS_SPEED;
    cin >> nums >> size;
    for(int i=0; i<nums; i++){
        cin >> new_num;
        lib.push_back(new_num);
    }
    for(int i=0; i<nums; i++){
        if(i>=size){
            if(min.front()<=i-size) min.pop_front();
            if(max.front()<=i-size) max.pop_front();
        }
        int new_elem = lib[i];
        while(1){
            if(min.empty()) break;
            if(new_elem>lib[min.back()]) break;
            min.pop_back();
        }
        min.push_back(i);
        while(1){
            if(max.empty()) break;
            if(new_elem<lib[max.back()]) break;
            max.pop_back();
        }
        max.push_back(i);
        if(i>=size-1){
            min_answ.push_back(lib[min.front()]);
            max_answ.push_back(lib[max.front()]);
        }
    }
    bool first = true;
    for(auto i: min_answ){
        if(!first) cout << " "; first = false; cout << i;
    }
    cout << "\n";
    first = true;
    for(auto i: max_answ){
        if(!first) cout << " "; first = false; cout << i;
    }
    cout << "\n";
    lib.clear(); min.clear(); max.clear(); min_answ.clear(); max_answ.clear();
}

int main()
{
    interface();
    return 0; 
}