思路

最简单的思路就是暴力进行计算，时间上可能会比较久，尤其是在给定的滑动窗口较大的情况下。 刷题比较多的小伙伴可以发现这是一道单调队列的典型题目，什么情况才满足双端队列呢？

• 滑动窗口如果只进元素的话，我们其实不用双端队列，只要保存一个最大值就可以了
• 但是滑动窗口如果是要退元素的话，就麻烦了起来，没有办法通过只保存一个值的方式来满足短时间复杂度的要求
• 所以考虑单调队列，并利用双端队列的性质维护这个单调队列

方法一：暴力解决

对每个滑动窗口都进行最大值的计算，最终结果返回到输出中

class Solution {
public:
    vector<int> maxInWindows(const vector<int>& num, unsigned int size) {
        vector<int> res;
        if(size == 0) return res;                                // 特殊情况处理
        int n = num.size();
        for(int i = size - 1; i < n; i++) {                      // i直接从窗口合法的位置开始向后遍历
            int l = i - size + 1;                                // 滑动窗口左指针
            int r = i;                                           // 滑动窗口右指针
            int mx = 0;
            for(int j = l; j <= r; j++) mx = max(mx, num[j]);    // 对每个滑动窗口计算最大值
            res.push_back(mx);                                   // 保存在输出中
        }
        return res;
    }
};

复杂度计算

• 时间复杂度：O(Nk)，双重循环，一层为N，内层为k。
• 空间复杂度：O(1)，不需要借助额外空间

方法二：单调队列

• 实际操作过程中我们没有考虑使用队列，而是利用一个数组的方式来模拟队列的进出，所以如果需要在双端操作的话需要引入left和right双指针作为队首队尾，在指针的移动过程中模拟队的出队入队过程
• 单调队列的思路：
  • 我们知道如果窗口中新进入了一个很大的数字A，则其前面的数字对于后面继续滑动来说完全没有作用了，所以不再考虑其他的小的数字
  • 当后面来的数字B、C、D等比A小，我们同样需要入队，因为在某个时刻A就会离开滑动窗口，继而的次大的数字在B、C、D等中
  • 由于我们维护的是单调递减的队列，所以队首的元素一定是当前滑动窗口中最大的元素，这是我们要维护单调队列的重要原因：我们想要通过取队首的这一简单操作的方式来拿到滑动窗口内的最大值。
• 单调队列的操作：
  • 我们维护一个单调递减的队列
  • 如果当前遍历的元素比最左端的元素都要大，则直接左指针移动到右指针的位置
  • 如果当前遍历的元素比单调队列中从右开始的数字大，就将单调队列中的数字逐个出队，直到其不能大过单调队列右边的第一个数字为止，此时将该数字入队
  • 每次遍历一个数字时（也就是滑动窗口移动一次时），判断队首元素是否还在窗口中（因此我们采用单调队列存储索引的方式而不是直接存储数值），如果在窗口中则取队首到最终结果即可，如果不在窗口中则要移动左指针，再取队首元素到最终结果中

class Solution {
public:
    vector<int> maxInWindows(const vector<int>& num, unsigned int size) {
        if(size == 1) return num;
        if(size == 0) return {};
        int n = num.size();
        vector<int> q(n+1);                                                //单调递减的队列
        vector<int> res;
        int left = 0;
        int right = 1;
        q[0] = 0;
        
        for(int i = 1; i < n; i++) {
            // 这里体现出双端队列的特性，左右都可以出队，入队都是从右侧入
            while(left < right && num[i] > num[q[left]]) left++;            //处理左指针队首指针
            while(right > left && num[i] > num[q[right -1]]) right--;       //处理右指针队尾指针
            q[right] = i;                                                   //处理好指针位置后加入新的满足单减的元素
            right++;
            while(q[left] <= i - (int)size) left++;                         //处理窗口大小问题，队列中的元素必须在窗口内
            if(i - (int)size + 1 >= 0) res.push_back(num[q[left]]);         //窗口形成的时间开始录入最终结果
        }
        return res;
    }
};

复杂度分析

• 时间复杂度：O(N)，将数组遍历一遍
• 空间复杂度：O(N)，用vector模拟N大小的队列