BM45. [滑动窗口的最大值]

https://www.nowcoder.com/exam/oj?tab=%E7%AE%97%E6%B3%95%E7%AF%87&topicId=295

BM45. 滑动窗口的最大值

https://www.nowcoder.com/practice/1624bc35a45c42c0bc17d17fa0cba788?tpId=295&sfm=discuss&channel=nowcoder

根据题意：
要寻找每个滑动窗口的最大值，每次只滑一位
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，双向队列最长时，将窗口填满