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

题意思路：
给定一个数组和滑动窗口的大小，找出所有滑动窗口里数值的最大值。

方法一:暴力枚举
每次选择枚举滑动窗口的起点，向后枚举 $k$ 个数字得到窗口中的最大值

复杂度分析

时间复杂度：O( $NK$ )， $N$ 表示数组的数量， $K$ 为滑动窗口大小

空间复杂度：O( $1$ )，存储结果的必要数组不算开辟额外空间

class Solution {
public:
    vector<int> maxInWindows(const vector<int>& num, unsigned int size) {
        int maxNUM=0;
        vector<int> ans;
        if(size==0)return ans;
        if(num.size()<size)return ans;//特判数组小于窗口大小的情况
        for(int i=0;i<=num.size()-size;i++){//遍历所有数字
            maxNUM=0;
            for(int k=i;k<size+i&&size+i-1<=num.size();k++){//枚举窗口内的所有数字
                maxNUM=max(maxNUM,num[k]);//比较最大值
            }
            ans.push_back(maxNUM);
        }
        return ans;
    }
};

方法二：单调队列

一、单调队列的概念：

单调队列，即单调递减或单调递增的队列。

二、单调队列的性质：

队列中的元素在原来的列表中的位置是由前往后的(随着循环顺序入队)。
队列中元素的大小是单调递增或递减的。

三、单调队列的特点：

从队尾入列，队首或队尾出列。

1）每次加入队列时先判断队列中的队尾是否小于当前元素，如果小于当前元素则一直弹出

2）将当前元素下标加入队列

3）再判断如果队头元素下标超过窗口大小则弹出队头元素

4）输出当前队头也就是滑动窗口的最大值

图文详解：
图片说明

复杂度分析

时间复杂度：O( $N$ )， $N$ 表示数组的数量

空间复杂度：O( $N$ )，每个值最多入队出队一次

class Solution {
public:
    vector<int> maxInWindows(const vector<int>& num, unsigned int size) {
       vector<int>ans;
        if(size==0||num.size()<size)return ans;
        deque<int> dq;
        for(int i=0;i<num.size();i++){
            while(dq.size()&&num[dq.back()]<num[i]){//每次加入队列时先判断队列中的队尾是否小于当前元素，如果小于当前元素则一直弹出
                dq.pop_back();
            }
            dq.push_back(i);//将当前元素下标加入队列
            while(dq.front()+size<=i){//再判断如果队头元素下标超过窗口大小则弹出队头元素
                dq.pop_front();
            }
            if(i+1>=size)ans.push_back(num[dq.front()]);//输出当前队头也就是滑动窗口的最大值

        }
        return ans;
    }
};