题解 | 滑动窗口的最大值

使用头尾都可以插删的双端队列，同时保证单调递减，这样头就是最大的了。

由于滑动窗口大小固定，我们可以直接在nun上原地修改，当然这样意义不大。

因为判断是否在窗口内的同时还要知道数值，存下标是自然的选择。

为什么判断pop_front是if而非while？因为窗口是一步一步往后移动的，元素自然也只需要一个一个离开。

class Solution {
public:
    vector<int> maxInWindows(vector<int>& num, int size) {
        int n=num.size();
        if (n==0||size==0)return {};
        deque<int>dq;
        // vector<int>ans;
        // for (int i=0;i<n;++i) {
        //     if (!dq.empty()&&dq.front()+size<=i)dq.pop_front();
        //     while (!dq.empty()&&num[i]>=num[dq.back()])dq.pop_back();
        //     dq.emplace_back(i);
        //     if (i>=size-1)ans.emplace_back(num[dq.front()]);
        // }
        // return ans;
        for (int i=0;i<n;++i) {
            if (!dq.empty()&&dq.front()+size<=i)dq.pop_front();
            while (!dq.empty()&&num[i]>=num[dq.back()])dq.pop_back();
            dq.emplace_back(i);
            if (i>=size-1)num[i-size+1]=num[dq.front()];
        }
        return vector<int>(num.begin(),num.end()-size+1);
    }
};