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

题目链接

https://www.nowcoder.com/practice/1624bc35a45c42c0bc17d17fa0cba788?tpId=13&&tqId=11217&rp=1&ru=/ta/coding-interviews&qru=/ta/coding-interviews/question-ranking
###题目描述
给定一个数组和滑动窗口的大小，找出所有滑动窗口里数值的最大值。

例如，如果输入数组{2,3,4,2,6,2,5,1}及滑动窗口的大小3，那么一共存在6个滑动窗口，他们的最大值分别为{4,4,6,6,6,5}；针对数组{2,3,4,2,6,2,5,1}的滑动窗口有以下6个： {[2,3,4],2,6,2,5,1}， {2,[3,4,2],6,2,5,1}， {2,3,[4,2,6],2,5,1}， {2,3,4,[2,6,2],5,1}， {2,3,4,2,[6,2,5],1}， {2,3,4,2,6,[2,5,1]}。

窗口大于数组长度的时候，返回空

方法一:

对于区间内求最值的题第一直觉就是直接暴力求解，也就是使用尺取(双指针)模拟求解。

思路分析

首先我们需要枚举出所有的区间，对每个枚举的区间暴力枚举求区间内的最大值，然后将每一个区间的最大值存入答案数组，将答案数组返回即可，而枚举区间的方法则可以通过枚举区间左端点l，然后根据区间长度算出对应的右端点r = l + size - 1即可, 并且要注意枚举过程中端点不能越界

代码和注释如下

class Solution {
public:
    vector<int> maxInWindows(const vector<int>& num, unsigned int size) {
        vector<int> ans;
        for(int l = 0; l < num.size() - size + 1; l ++ ) { //枚举左端点
            int r = l + size - 1;                          //计算出对应的右端点
            int maxn = -1;
            for(int i = l; i <= r; i ++ ) maxn = max(maxn, num[i]); //暴力求出每个区间内部的最值
            if(maxn != -1) ans.push_back(maxn);            //将每个区间的最值存入结果数组
        } 
        return ans;
    }
};

时间复杂度分析:

我们枚举的时间即为枚举端点与每个区间确定后求内部最值的时间，故时间复杂度为O(nk)
空间复杂度为O(n)

方法二:使用单调队列求解

对于滑动窗口背景类问题，我们可以通过单调队列这一数据结构高效的求出最值

思路分析

介绍:

单调队列是一种高效处理求滑动窗口最值的数据结构，其本身是一个双端队列(deque)，其可以通过O(n)的线性时间复杂度求出最值

原理分析
我们给出一组数据[2,3,4,2,6,2,5,1],窗口大小为3,现在我们分析一下单调队列在O(n)复杂度内完成最值维护的原理:

首先通过对数据的观察可知:随着窗口的滑动，若后面出现了更大的数，则这个数前面所有在窗口中的数都不可能是最大值
我们可以举例说明:(假设【】代表滑动窗口)
假设某时刻窗口滑至当前状态，可以看到此时窗口中的数为【3, 4, 2】，而下一个即将进入窗口的数为6，比当前窗口中的数都大
当6进入窗口后，6之前且还在窗口中的数因为小于6，故一定不可能是最大值，因为在窗口中一定有一个6比他们大

于是我们可以得到这样一个性质：
如果队列中存在两个元素，满足 a[i] >= a[j] 且 i < j，那么a[j]将不可能作为窗口中的最大值，此时可以直接将 a[j] 删掉；通过这样的操作队列中剩下的元素严格单调递减，故队头就是整个队列中的最大值，求窗口的最值也可以直接通过O(1)的复杂度访寻。
而维护出这种队列的方法只需要我们在往队尾插入元素之前，先将队尾大于等于当前数的元素全部弹出即可

代码与注释如下

class Solution {
public:
    vector<int> maxInWindows(const vector<int>& num, unsigned int size)
    {
        vector<int> ans;
        deque<int> que;
        for(int i = 0; i < num.size(); i ++ ) {  //枚举窗口右端 
            //队头是否出队 和 更新队头
            while(!que.empty() && i - que.front() + 1 > size)  que.pop_front();
            //保证队列的单调性
            while(!que.empty() && num[que.back()] <= num[i])  que.pop_back();
            //新元素入队    
            que.push_back(i);
            //当前遍历的长度大于等于窗口窗口长度才开始存储答案
            if(size && i >= size - 1)  ans.push_back(num[que.front()]);
        }
        return ans;
    }
};

注意:

构造单调队列时，因为原数组可能出现相同的值的元素，故通常在单调队列中存储的时原数组元素的下标，保证唯一性。

时间复杂度分析:

因为维护单调队列的过程中是线性的遍历一遍元数组，每个元素只被访问一次，故复杂度为O(n)
空间复杂度为O(n)