思路

根据题意：要寻找每个滑动窗口的最大值，每次只滑一位 size等于0或者大于数组长度，都返回空值

方法一：暴力法 暴力解法应该是最容易想到的，只需要遍历数组的同时往后遍历每个窗口，找出最大值即可。

class Solution {
public:
    vector<int> maxInWindows(const vector<int>& num, unsigned int size) {
        vector<int> res;
        if(size <= num.size() && size != 0) //窗口大于数组长度的时候，返回空
            for(int i = 0; i <= num.size() - size; i++){//数组后面要空出窗口大小，避免越界
                int max = 0; //寻找每个窗口最大值
                for(int j = i; j < i + size; j++){
                    if(num[j] > max)
                        max = num[j];
                }
                res.push_back(max);
            }
        return res;
    }
};

复杂度分析

时间复杂度：O(nm)，其中n为数组长度，m为窗口长度，双层for循环
空间复杂度：O(1)，没有使用额外的空间，暂存的结果res不算入空间开销

方法二：双向队列法 暴力法重复计算了很多不必要比较。我们都知道，若是一个数字A进入窗口后，若是比窗口内其他数字都大，那么这个数字之前的数字都没用了，因为它们必定会比A早离开窗口，在A离开之前都争不过A，所以A在进入时要依次从后排除掉前面的小值。而当一个窗口最前的数字要离开时，是从前面离开。因此一个双向队列可以解决这个问题。图片说明 具体做法： 维护一个双向队列，用来存储数列的下标，如果即将进入队列的下标的值大于队列后方的值，依次将它们pop掉，再加入。如果某个下标已经过了窗口，则从队列前方将其pop掉。

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;
    }
};

复杂度分析：

时间复杂度：O(n)，只遍历一遍数组
空间复杂度：O(m)，窗口长度m，双向队列最长时，将窗口填满

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

思路