题解 | 【模板】滑动窗口

#include <algorithm>
#include <deque>
#include <ios>
#include <iostream>
#include <vector>
using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int n, k;
    cin >> n >> k;
    vector<int > s(n);
    for (int i = 0; i < n; i++) {
        cin >> s[i];
    }
    deque<int > a; // 只存储下标，因为滑动窗口遍历时只有下标可以作为参考系
    vector<int> result;
    for (int i = 0; i < n; i++) { // 初始左指针为-k+1, 右指针为0
        while (!a.empty() && s[a.back()] < s[i]) {
            a.pop_back();
        } // 队列非空，且队尾元素小于当前遍历到的s[i]，那保持弹出元素，使得队列始终单调
        a.push_back(i); // 队列只存储下标

        if (a.front() <= i-k) { 
            // 队首元素代表最大元素的下标，因为最大元素已经不在滑动窗口内，所以及时弹出
            a.pop_front();
        }
        
         if (i >= k-1) { // 左指针终于非负，滑动窗口终于形成
            result.push_back(s[a.front()]); // result记录当前窗口最大元素
        }
        // 两个if语句的顺序不可调换：先保证了队首的合法性，才能取出正确的值。
        
    }
    // 以上这番操作，使得新的可能的最大元素的下标及时从队尾流入，
    // 同时淘汰掉队列里所有比它小的元素的下标，这样最大元素值的下标就能不断上游。
    // 同时保持对队首元素的监控，如果队首元素下标已经小于左指针，那么及时弹出，
    // 保证最大元素均位于滑动窗口内，每次遍历就能将当前滑动窗口内的最大元素压入result数组里

    // 如果采用for循环遍历窗口，采用max_element s[i]找到最大元素这种暴力求解，
    // 它会重复遍历上个滑动窗口和当前滑动窗口内重合的元素，这是不必要的时间浪费
    // 而采用双端队列deque，每个元素只会最多被操作两次（压入和弹出），节省了不少时间

    for (const int &i : result) {
        cout << i << " ";
    }
    return 0;
}