题解 | #滑动窗口的最大值#

class Solution {
public:
    vector<int> maxInWindows(const vector<int>& num, unsigned int size) {
        vector<int> res;
        // 窗口大于数组长度的时候，返回空
        if(size <= num.size() && size > 0){
            // 双向队列
            deque<int> dq;
            // 先遍历一个窗口
            for(int i = 0; i < size; ++i){
                // 去掉比自己先进队列的小于自己的值
                while(!dq.empty() && num[dq.back()] < num[i])
                    dq.pop_back();
                dq.push_back(i);
            }
            // 遍历后续数组元素
            for(int i = size; i < num.size(); ++i){
                res.push_back(num[dq.front()]);
                while(!dq.empty() && dq.front() < (i - size + 1))
                    // 弹出窗口移走后的值
                    dq.pop_front();
                // 加入新的值前，去掉比自己先进队列的小于自己的值
                while(!dq.empty() && num[dq.back()] < num[i])
                    dq.pop_back();
                dq.push_back(i);
            }
            res.push_back(num[dq.front()]);
        }
        return res;
    }
};