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

一.题意整理

给定一个数组num和一个窗口大小size，求每个连续size序列的最大值。

二.思路整理

首先指出利用c++STL中的max_element也可以AC本题，但是很显然时间复杂度比较高。那么我们可以采用滑动窗口算法来解决，滑动窗口算法本质就是对区间进行扩张和放缩，下面给出滑动窗口的框架

int left = 0, right = 0;
while (right < s.size()) {
     while (window needs shrink) {//对于是否需要进行缩小
        // 缩小窗口
        window.remove(s[left]);
        left++;
    }
    // 增大窗口
    window.add(s[right]);
    right++;
    
    
}
//逻辑框架 结合具体情况而言

对于该题我们最重要的就是维护区间的最大值，我们可以利用双端队列来实现。双端队列是一个可以实现双端插入和删除的队列。我们将会存储每一个数据的下标，既方便比较其是否在区间内又可以快速表示其对应的值。队列中数组下标应当是依次递减的，这是为了通过下标保存当前这个区间下，最大元素的下标始终在队头。对于队列中的元素最需要维护的就是最大值，每一次插入新数据的时候，小于新数据的数据就没有存在的意义可以对其进行出队操作。

下面总结整题思路：

1.双端队列是空，或者当前数据小于队尾的最小数据，直接从队尾入队。
2.双端队列不是空的时候，比较队尾数据，若队尾小于插入元素队尾出队，至队尾元素大于插入元素。
3.由于前面的维护，队头就一直是最大元素。

三.代码实现

class Solution {
public:
    vector<int> maxInWindows(const vector<int>& num, unsigned int size) {
        vector<int>ans;//用来返回最后的最大值
        deque<int>q;
        if(size==0) return ans;
        int i=0;
        while(i<num.size()){
            //缩小窗口
            while(q.size()&&num[q.back()]<num[i]){
                q.pop_back();
            }
            q.push_back(i);
            //说明当前队头已经不在区间中之间出队
            if(q.front()+size<=i){
                q.pop_front();
            }
            //记录最大值
            if(i+1>=size){
                ans.push_back(num[q.front()]);
            }
            i++;
        }
        return ans;
    }
};