题解 | 【模板】滑动窗口

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

vector<int> max_slip_window(vector<int>& nums, int k)
{   
    int n = nums.size();
    //双端队列里维持严格从大到小排列的数字的下标
    //如果即将进队列的元素比较大，就一直从尾部弹出，保证队列里都是严格“大压小”
    //这样队首指针一直指向的就是窗口内的最大值
    //如果l指针指向的是窗口内最值，就从“队首”弹出。
    //然后l++，r++，直到r来到最后一个元素，收集完最值，结束。
    deque<int> dq;
    for (int i = 0; i<k-1; ++i)
    {
        
        while (!dq.empty() && nums[dq.back()] <= nums[i])
        {
            dq.pop_back();
        }
        dq.push_back(i);
    }

    //此时窗口大小是k-1个元素
    //每次r进窗口，收集窗口内最值
    vector<int> ans;
    for (int l = 0, r = k-1; r < n; ++r)
    {
        while (!dq.empty() && nums[dq.back()] <= nums[r])
        {
            dq.pop_back();
        }
        dq.push_back(r);
        ans.push_back(nums[dq.front()]);

        if (l++ == dq.front())
        {
            dq.pop_front();
        }
    }

    return ans;

}


int main() {
    int n,k;
    cin >> n >> k;
    vector<int> nums(n);
    for (auto& num : nums)
    {
        cin >> num;
    }

    vector<int> ans = max_slip_window(nums, k);
    for (auto& n : ans)
    {
        cout << n << " ";
    }
}
// 64 位输出请用 printf("%lld")