牛客热题：滑动窗口的最大值

📟作者主页：慢热的陕西人

🌴专栏链接：力扣刷题日记

📣欢迎各位大佬👍点赞🔥关注🚓收藏，🍉留言

牛客热题：滑动窗口的最大值

题目链接

滑动窗口的最大值_牛客题霸_牛客网 (nowcoder.com)

方法一：暴力

思路

• 枚举每个区间的起始
  • 然后遍历每个区间获取最大值放入到ret中

代码

vector<int> maxInWindows(vector<int>& num, int size) {int n = num.size();vector<int> ret;if(size == 0 || size > n) return ret;for(int i = 0 ; i + size - 1 < n; ++i){int max_val = -10010;for(int j = 0; j < size; ++j){max_val = max(max_val, num[i + j]);}ret.push_back(max_val);}return ret;}

复杂度

时间复杂度：O(N * M) ,其中N是数组的长度，M为size的大小

空间复杂度：O(N), 使用了一个N - size长度的数组用来返回答案

方法二：单调双端队列

思路

• step1：对于数组长度为0，窗口长度为0，或者窗口长度超过num的直接返回空数组
  • step2：遍历数组，维护单调队列，将队列尾部小于当前数组元素的值全部出队。
  • step3：将当前值入队尾部
  • step4：判断当前对头的下标是否超过区间长度的限制，如果超过则出队头
  • step5：当前遍历的数组下标大于等于区间的长度，那么则将对头放入到答案数组
• step6：遍历结束，返回答案数组即可

代码

    vector<int> maxInWindows(vector<int>& num, int size) {int n = num.size();vector<int> ret; deque<int> dp;if(n == 0 || size == 0 || size > n) return ret;for(int i = 0; i < n; ++i){//除去队列中比当前值小的值while(!dp.empty() && num[dp.back()] < num[i])dp.pop_back();//将当前下标入队列dp.push_back(i);//判断队列头部的下标是否超过序列长度if(i - dp.front() >= size)dp.pop_front();//将最大值放入到答案中if(i + 1 >= size)ret.push_back(num[dp.front()]);}return ret;}

复杂度

时间复杂度：O(N), 遍历了一遍数组，求出了所有滑动窗口的最大值

空间复杂度：O(N)，其中开辟了N - size大小的答案数组，和最大为size长度的双端队列