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

滑动窗口的最大值：最直观的想法是，两层for循环，外层i表示每次窗口的起始位置，内层j表示每次窗口的结束位置，遍历窗口内的每一个元素，然后取窗口内的最大值，并加入到结果数组中。注意，当数组为空时或者滑动窗口值大于数组长度，要返回空数组。(牛客这个暴力方法居然过啦)

vector<int> maxInWindows(const vector<int>& num, unsigned int size) 
{
     vector<int> res;
     // 数组为空 或者 滑动窗口值大于数组长度
     if(num.size()==0||size>num.size())
        return res;
     int maxn;
     // i表示起始位置
     for(int i=0;i+size-1<num.size();i++)
     {
         maxn=num[i];
         // j表示结束位置 遍历整个窗口
         for(int j=i+1;j<=i+size-1;j++)
         {
            maxn=max(num[j],maxn);
         }
         // 将最大值加入结果
         res.push_back(maxn);
     }
     return res;
}

优化：上述方法其实包含很多重复计算，我们可以通过分析来优化。如果当前元素大于前面元素，那么前面的元素不可能成为最大值，故需要将前面的元素从队尾出队；如果当前元素小于等于前面元素，那么需要将元素从队尾入队，因为该元素可能会成为后续的最大值。同时，我们要判断窗口内元素是否过期，即队头元素下标是否小于当前窗口左端，由于要方便统计窗口边界，故使用的是下标存储，当超过边界不合法时需要从队头出队；最后要判断当前元素下标是否满足一个窗口长度，因为只有有窗口才可以将当前窗口内的最大值加入结果数组。注意，使用的是双端队列！这样就维护了一个长度为size的单调递减队列，每次都从队头取窗口内的最大值！

vector<int> maxInWindows(const vector<int>& num, unsigned int size) 
{
     vector<int> res;
     // 数组为空 或者 滑动窗口值大于数组长度
     if(num.size()==0||size>num.size())
        return res;
     // 双端队列
     deque<int> dq;
     for(int i=0;i<num.size();i++)
     {
        // 如果当前元素大于之前的 则将之前的元素依次从队尾弹出 从而保证维护的是单调递减队列
        while(!dq.empty()&&num[i]>num[dq.back()])
           dq.pop_back();
        // 将元素下标入队 以便后续判断元素是否在窗口内
        dq.push_back(i);
        // 若队头元素不合法就从队头弹出 双端队列维持长度为size 队首小于窗口左端则过期
        if(i-dq.front()+1>size)
           dq.pop_front();
        // 当满足窗口长度时就将窗口最大值加入结果数组
        if(i>=size-1)
           res.push_back(num[dq.front()]);
     }
     return res;
}