题解 | #滑动窗口的最大值# 基于双向队列

#include <deque>
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param num int整型vector 
     * @param size int整型 
     * @return int整型vector
     */
    vector<int> maxInWindows(vector<int>& num, int size) {
        // write code here
        vector<int> res;
        int n = num.size();
        if(size > n || size <= 0) return res;
        // 注意这里返回的是下标而不是元素值，因为通过下标可以比较方便地寻找元素值
        deque<int> deq;
        for(int i=0; i<n; i++){
            // 处理需要排除的元素的逻辑
            // 注意这里的判断条件是>=
            if(!deq.empty() && i-size >= deq.front()){
                deq.pop_front();
            }
            // 处理加入元素并维持队首元素最大的逻辑
            // 注意这里的判断条件是<=，且使用的是while循环
            while(!deq.empty() && num[deq.back()] <= num[i]){
                deq.pop_back();
            }
            deq.push_back(i);

            if(i >= size -1 ){
                res.push_back(num[deq.front()]);
            }
        }
        return res;
    }
};