c++双端队列

参考精华解答，时间复杂度O(n)，空间复杂度O(n)，记录一下，熟悉解题思路

用双端队列保存数组元素下标。队列中数组下标对应元素应当是递减的，这是为了通过下标保存当前这个window下，最大、第二大、第三大……的元素。最大元素的下标始终在队头。

• 如果队列为空，或者当前元素小于队尾对应的元素，把当前元素的下标加入队尾。
• 否则，循环判断，如果当前元素大于队尾对应的元素，则队尾出队列，直至小于队尾对应的元素或队列为空。
• 如果队头元素，即最大元素在window最左边，弹出队头。
• 如果window已形成，则把队头元素加入队列。

class Solution {
public:
    vector<int> res;
    deque<int> dq;
    
    vector<int> maxInWindows(const vector<int>& num, unsigned int size) {
        int cnt = num.size();
        if(num.empty() || size == 0 || cnt < size) return res;
        for(size_t i = 0; i < cnt; i++){
            while(!dq.empty() && num[dq.back()] < num[i]){
                dq.pop_back();
            }
            dq.push_back(i);
            if(dq.front() + size <= i){
                dq.pop_front();
            }
            if(i +1 >= size){
                res.push_back(num[dq.front()]);
            }
            
        }
        return res;
    }

};