class Solution {
public:
    vector<int> maxInWindows(vector<int>& nums, int k) {
        //用一个双端队列存储数据下标，这个双端队列是一个单调队列，后的下标代表元素的值总大于前面的
        vector<int> res;
        deque<int> q; //存下标
        for(int  i = 0;i < nums.size();++i){
            while(!q.empty() && q.front() <= i - k)    q.pop_front();   //若大于等于滑动窗口大小，弹出队头

            //如果队尾元素小于当前元素，弹出队尾，从而维护单调性，后面的都大于前的
            while(!q.empty() && nums[q.back()] <= nums[i]) q.pop_back();

            q.push_back(i);
            if(i >= k - 1) res.push_back(nums[q.front()]);
        }
        return res;
    }
};