双端队列

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

void getMaxWindow(vector<int>& nums,vector<int>& res,int w){
    if(nums.size() == 0 || w < 1 || nums.size() <  w){
        return;
    }
    deque<int> q;
    for(int i = 0; i < nums.size(); ++i){

        //如果队尾的元素比当前的元素小，将队尾元素弹出，目的就是为了让队头保持最大值
        while(!q.empty() && nums[i] > nums[q.back()]){
            q.pop_back();
        }
        //这个时候要么队列为空，要么当前元素小于等于队尾元素
        q.push_back(i);
        //现在需要判断当前下标是否过期
        //已经过期
        if(q.front() == i - w){
            q.pop_front();
        }
        //从下标为 w-1 的坐标开始每次都有窗口最大值
        if(i >= w - 1){
            res.push_back(nums[q.front()]);
        }
    }

}

int main(){

    int n,w;
    while(cin >> n >> w){

        vector<int> nums(n);
        for(int i = 0; i < n; ++i){
            cin >> nums[i];
        }
        vector<int> res;
        getMaxWindow(nums,res,w);
        for(int i = 0; i < res.size(); ++i){
            cout << res[i] << " ";
        }
        cout << endl;
    }
    return 0;
}