Solution

• 构建单调队列

class Solution {
public:
    class monotonicQueue {
    public:
        deque<int> que;    // 借助双端队列构造单调队列
        
        void push(int num) {
            while (!que.empty() && que.back() < num) {
                que.pop_back();
            }
            que.push_back(num);
        }
        
        void pop(int num) {
            if (!que.empty() && que.front() == num) {
                que.pop_front();
            }
        }
        
        int front() {
            return que.front();
        }
    };
    
    vector<int> maxInWindows(const vector<int>& num, unsigned int size) {
        vector<int> res;
        int n = num.size();
        if (n == 0 || size <= 0 || n < size) return res;
        
        monotonicQueue que;
        for (int i = 0; i < n; ++i) {
            que.push(num[i]);
            if (i + 1 >= size) {
                res.push_back(que.front());
                que.pop(num[i + 1 - size]);
            }
        }
        return res;
    }
};

• 直接使用双端队列保存索引值

class Solution {
public:
    vector<int> maxInWindows(const vector<int>& nums, unsigned int k) {
        int n = nums.size();
        if (n < k || k == 0) return {};
        deque<int> q;  // 保存的是索引值
        for (int i = 0; i < k; ++i) {
            while (!q.empty() && nums[i] >= nums[q.back()]) {
                q.pop_back();
            }
            q.push_back(i);
        }

        vector<int> res;
        res.push_back(nums[q.front()]);
        for (int i = k; i < n; ++i) {
            while (!q.empty() && nums[i] >= nums[q.back()]) {
                q.pop_back();
            }
            q.push_back(i);
            while (q.front() <= i-k) {
                q.pop_front();
            }
            res.push_back(nums[q.front()]);
        }
        return res;
    }
};